题解：CF2183C War Strategy

aTawa · 2026-07-24 08:07:08 · 题解

洛谷 链接

codeforces 链接

题意简述

• 有 n 个基地排成一行，第 k 个为主基地。初始仅主基地有 1 名士兵。
• 每天按顺序发生：
  1. 选择一个基地 i，从该基地选任意数量士兵（可为 0 或全部），统一向左或向右移动一格（不能越界）。
  2. 一名新士兵加入主基地 k（当天不能被调动）。
• 共 m 天，目标是在第 m 天结束时让尽可能多的基地至少有一名士兵（被加固）。求最大被加固基地数。

数据范围：1 \le n \le 10^5，1 \le m \le 10^9，1 \le t \le 10^4，\sum n \le 2 \times 10^5。

思路

模拟赛 T1。

不难发现，对于所有士兵都在一个点上，可以以数量递减，移动方向逐渐向远方的方案，使得原来在一个点上的士兵被摊平。

如，假设一开始是 3，并且为了便于演示，士兵不再增加。第一步将其向远方移动 2 个士兵，变为 12。第二步将有 2 个士兵的点向远方移动 1 个士兵，变为 111。

发现一种没有左右端点限制下的构造方案：先让一个士兵一直往一个方向移动，构成 10...0x 的局面。设这个士兵离主基地的距离是 dis，这样需要 dis 天时间，士兵和基地之间有 dis-1 个 0。这个时候就把基地位置的士兵挪到 1 之前，变成 11...1x 的局面。此时再用基地的士兵向另一个方向推平，长度是 dis，代价是 dis。

这种方案下让左右的距离都是 dis 的代价是 3\times dis-1，让 dis 加上 1 的额外代价是 3。如果再细一点，一个端点让 dis 增加 1 的代价是 2，另外一个端点的代价是 1。

如果有限制，就不能在第二个端点以代价 1 使得端点长度增加 1。

代码实现：如果左右端点有至少一个没有被限制且此时 m\geq2， 找到一个没有被限制的端点拓展 1 长度，m 减去代价 2。如果此时另外一个端点没有被限制，则其拓展 1 长度，m 减去代价 1。

代码

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pii pair<int,int>
#define f(i,a,b) for(int i=(a);i<=(b);i++)
#define Dl(a) cout << #a << " : " << a << "\n";
#define D(a) cout << #a << " : " << a;
#define Da(a,i,j) cout << #a << " : ";f(idx,i,j){cout << a[idx] <<" ";}
int t;
int n,k,m;
signed main(){
    // freopen("colony.in","r",stdin);
    // freopen("colony.out","w",stdout);
    cin >> t;
    while (t--){
        cin >> n >> m >> k;
        int l = k,r = k;
        int ans = 0;
        m += 1;
        while (m >= 2 && (l > 1 || r < n)){
//          Dl(m);Dl(l);Dl(r);
            if (l > 1 && r < n && m >= 3){
                m -= 3;
                ans += 2;
                l --;
                r ++;
            }
            else if (l > 1){
                m -= 2;
                l--;
                ans ++;
            }
            else if (r < n){
                m -= 2;
                r ++;
                ans++;
            }
        }
        cout << ans + 1<< "\n";
    }
    return 0;
}