Hello 2026——C. War Strategy（二分答案可以减小实现难度） · znzryb
## 题目大意
### 背景
有 n 个基地排成一条线，第 k 个基地是主基地(home base)。初始时主基地有 1 个士兵。
### 规则
每天按顺序发生以下事件:
1. 选择一个基地 i 和该基地中任意数量的士兵(可以是 0 或全部)，命令这些士兵向左移动到基地 i-1 或向右移动到基地 i+1(所有士兵必须同方向移动，且不能移出边界)
1. 然后，一个新士兵出现在主基地 k(这个新士兵不受当天命令影响)
### 目标
给定:
- n: 基地总数
- m: 天数
- k: 主基地位置
如果一个基地至少有 1 个士兵，则称其为"加固基地"(fortified)。求第 m 天结束时最多能有多少个加固基地。
### 输入输出
**输入:** 多组测试数据，每组包含三个整数 n, m, k (1≤k≤n≤10⁵, 1≤m≤10⁹)
**输出:** 每组数据输出第 m 天结束时最多能加固的基地数量
### 限制
- 1 ≤ t ≤ 10⁴ (测试用例数)
- 1 ≤ k ≤ n ≤ 10⁵
- 1 ≤ m ≤ 10⁹
- 所有测试用例的 n 之和不超过 2×10⁵
[https://generals.io/](https://generals.io/) 应该是从这个游戏获取的灵感。
## 思路讲解
其实就是贪心，不过我们一开始写的贪心代码太屎山了，过不去，我重构了一下，写成了一个**二分答案**的代码，一次就过了。
那么二分答案，我们已经知道了这个需要占据 $occupied$ 个位置了，还有什么变量是不确定的吗？当然是有的，就是左边要占据多少个位置（$needl$），右边要占据多少个位置（$needr$）。 不过为了方便期间，我们定义左边为空比较少的（$reml$），右边为空比较多的（$remr$），即 $remr>reml$。使用以下式子计算出 $needl$ 和 $needr$：
$$
reml\times2<occupied:needl\gets reml,needr\gets occupied-needl\\
\text{others}:needl\gets\frac{occupied}{2},needr\gets occupied-needl
$$
那么，我们已经知道了 $needl$ 和 $needr$，那我们知道，最好的走法就是先走 $needr$，然后再走 $needl$，由于 $needr≥needl$，我们可以保证走左边的时候出兵点有足够的兵。因此，总的消耗为：
$$
consume\gets needl+needr+(needr-1)
$$
那么最后 $consume$ 和 $m$ 比较一下就好了，那么 check 函数写出来了，整个二分答案就没有难点了。
⚠️注意：我们对传入的参数 $occupied$ 减了 1，因为出兵点是自动占领的嘛。
```cpp
auto check=[&](ll occupied) {
if (occupied>N) return false;
occupied--;
ll reml=max(0ll,K-1),remr=max(0ll,N-K);
if (reml>remr) {
swap(reml,remr);
}
ll needl=0,needr=0;
if (reml*2<occupied) {
needl=reml;
needr=occupied-reml;
}else {
needl=occupied/2;
needr=occupied-needl;
}
ll consume=needl+needr*2-1;
if (consume>M) {
return false;
}
return true;
};
```
## AC代码
AC
[https://codeforces.com/contest/2183/submission/358159596](https://codeforces.com/contest/2183/submission/358159596)
::: 源代码
```cpp
/**
* Problem: C. War Strategy
* Contest: Hello 2026
* Judge: Codeforces
* URL: https://codeforces.com/contest/2183/problem/C
* Created: 2026-01-17 10:38:08
* Author: Gospel_rock
*/
#include <bits/stdc++.h>
#include <ranges>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT;
/*
*
*/
void Solve() {
ll N,M,K;
cin >> N >> M >> K;
ll bsl=1,bsr=N;
auto check=[&](ll occupied) {
if (occupied>N) return false;
occupied--;
ll reml=max(0ll,K-1),remr=max(0ll,N-K);
if (reml>remr) {
swap(reml,remr);
}
ll needl=0,needr=0;
if (reml*2<occupied) {
needl=reml;
needr=occupied-reml;
}else {
needl=occupied/2;
needr=occupied-needl;
}
ll consume=needl+needr*2-1;
if (consume>M) {
return false;
}
return true;
};
while (bsl<bsr) {
ll mid=(bsl+bsr+1)>>1;
if (check(mid)) {
bsl=mid;
}else {
bsr=mid-1;
}
}
cout<<bsl<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> lT;
while(lT--)
Solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2183/submission/358159596
*/
```
:::
## 心路历程（WA，TLE，MLE……）