题目大意
背景
有 n 个基地排成一条线，第 k 个基地是主基地(home base)。初始时主基地有 1 个士兵。
规则
每天按顺序发生以下事件:
-
选择一个基地 i 和该基地中任意数量的士兵(可以是 0 或全部)，命令这些士兵向左移动到基地 i-1 或向右移动到基地 i+1(所有士兵必须同方向移动，且不能移出边界)
-
然后，一个新士兵出现在主基地 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/ 应该是从这个游戏获取的灵感。
思路讲解
其实就是贪心，不过我们一开始写的贪心代码太屎山了，过不去，我重构了一下，写成了一个二分答案的代码，一次就过了。
那么二分答案，我们已经知道了这个需要占据 occupied 个位置了，还有什么变量是不确定的吗？当然是有的，就是左边要占据多少个位置（needl），右边要占据多少个位置（needr）。 不过为了方便期间，我们定义左边为空比较少的（reml），右边为空比较多的（remr），即 remr>reml。使用以下式子计算出 needl 和 needr：
reml×2<occupied:needl←reml,needr←occupied−needlothers:needl←2occupied,needr←occupied−needl
那么，我们已经知道了 needl 和 needr，那我们知道，最好的走法就是先走 needr，然后再走 needl，由于 needr≥needl，我们可以保证走左边的时候出兵点有足够的兵。因此，总的消耗为：
consume←needl+needr+(needr−1)
那么最后 consume 和 m 比较一下就好了，那么 check 函数写出来了，整个二分答案就没有难点了。
⚠️注意：我们对传入的参数 occupied 减了 1，因为出兵点是自动占领的嘛。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 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
源代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
#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 CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353;
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;
}
|
心路历程（WA，TLE，MLE……）