[CSP-S2020] 贪吃蛇
题目描述
草原上有 \(n\) 条蛇，编号分别为 \(1, 2, \ldots , n\)。初始时每条蛇有一个体力值 \(a_i\)，我们称编号为 \(x\) 的蛇实力比编号为 \(y\) 的蛇强当且仅当它们当前的体力值满足 \(a_x > a_y\)，或者 \(a_x = a_y\) 且 \(x > y\)。
接下来这些蛇将进行决斗，决斗将持续若干轮，每一轮实力最强的蛇拥有选择权，可以选择吃或者不吃掉实力最弱的蛇：
- 如果选择吃，那么实力最强的蛇的体力值将减去实力最弱的蛇的体力值，实力最弱的蛇被吃掉，退出接下来的决斗。之后开始下一轮决斗。
- 如果选择不吃，决斗立刻结束。
每条蛇希望在自己不被吃的前提下在决斗中尽可能多吃别的蛇（显然，蛇不会选择吃自己）。
现在假设每条蛇都足够聪明，请你求出决斗结束后会剩几条蛇。
本题有多组数据，对于第一组数据，每条蛇体力会全部由输入给出，之后的每一组数据，会相对于上一组的数据，修改一部分蛇的体力作为新的输入。
输入格式
第一行一个正整数 \(T\)，表示数据组数。
接下来有 \(T\) 组数据，对于第一组数据，第一行一个正整数 \(n\)，第二行 \(n\) 个非负整数表示 \(a_i\)。
对于第二组到第 \(T\) 组数据，每组数据：
第一行第一个非负整数 \(k\) 表示体力修改的蛇的个数。
第二行 \(2k\) 个整数，每两个整数组成一个二元组 \((x,y)\)，表示依次将 \(a_x\) 的值改为 \(y\)。一个位置可能被修改多次，以最后一次修改为准。
输出格式
输出 \(T\) 行，每行一个整数表示最终存活的蛇的条数。
样例 #1
样例输入 #1
2
3
11 14 14
3
1 5 2 6 3 25
样例输出 #1
3
1
样例 #2
样例输入 #2
2
5
13 31 33 39 42
5
1 7 2 10 3 24 4 48 5 50
样例输出 #2
5
3
样例 #3
样例输入 #3
见附件中的 snakes/snakes3.in
样例输出 #3
见附件中的 snakes/snakes3.ans
样例 #4
样例输入 #4
见附件中的 snakes/snakes4.in
样例输出 #4
见附件中的 snakes/snakes4.ans
提示
【样例 #1 解释】
第一组数据，第一轮中 \(3\) 号蛇最强，\(1\) 号蛇最弱。若 \(3\) 号蛇选择吃，那么它将在第二轮被 \(2\) 号蛇吃掉。因此 \(3\) 号蛇第一轮选择不吃，\(3\) 条蛇都将存活。
对于第二组数据，\(3\) 条蛇体力变为 \(5, 6, 25\)。第一轮中 \(3\) 号蛇最强，\(1\) 号蛇最弱，若它选择吃，那么 \(3\) 号蛇体力值变为 \(20\)，在第二轮中依然是最强蛇并能吃掉 \(2\) 号蛇，因此 \(3\) 号蛇会选择两轮都吃，最终只有 \(1\) 条蛇存活。
【数据范围】
对于 \(20 \%\) 的数据，\(n = 3\)。
对于 \(40 \%\) 的数据，\(n \le 10\)。
对于 \(55 \%\) 的数据，\(n \le 2000\)。
对于 \(70\%\) 的数据，\(n \le 5 \times {10}^4\)。
对于 \(100\%\) 的数据：\(3 \le n \le {10}^6\)，\(1 \le T \le 10\)，\(0 \le k \le {10}^5\)，\(0 \le a_i, y \le 10^9\)。保证每组数据（包括所有修改完成后的）的 \(a_i\) 以不降顺序排列。
Solution
神一样的贪心题。
对于这道题，有一个很强的贪心结论，就是对于最强的蛇，如果吃掉最弱的蛇后不会成为最弱的蛇，那么这条蛇一定会选择吃。
考虑怎么证明这个结论。假设当前最强蛇为 \(A\)，次强蛇为 \(B\)，如果 \(A\) 吃掉最弱的蛇后仍然比 \(B\) 强，那么 \(A\) 肯定会选择吃。如果吃了过后比 \(B\) 更弱了，那么现在的最强蛇就变成了 \(B\)，并且如果 \(B\) 选择了吃的话一定会变得比 \(A\) 更弱（初始值比 \(A\) 小，吃的比 \(A\) 大，最终就比 \(A\) 弱），所以如果 \(B\) 选择吃了过后，如果 \(B\) 没事，\(A\) 也一定没事。所以只要吃了过后不会变成最弱的蛇，\(A\) 都一定会选择吃。
然后来考虑如果 \(A\) 吃了最弱的蛇过后成为了最弱的蛇的话 \(A\) 会怎么选择。
-
\(2\) 条蛇的时候，假设此时的蛇为 \(A,B\)，更强的蛇为 \(B\)，那么此时 \(B\) 一定会选择吃，因为吃了就变成最后一条蛇，不会再被吃掉。
-
\(3\) 条蛇的时候，假设多的一条蛇为 \(C\)，并且 \(C\) 最强，那么 \(C\) 知道，如果自己吃了 \(A\) 的话，会变成 \(2\) 条蛇的情况，也就是自己一定会被 \(B\) 吃掉，所以为了保证自己不被吃掉，\(C\) 会选择不吃。
-
\(4\) 条蛇的时候，假设多的一条蛇为 \(D\)，并且 \(D\) 最强，那么 \(D\) 也知道，即使自己吃了 \(A\)，\(C\) 也不敢吃掉自己，因此 \(D\) 一定会选择吃。
-
\(\cdots\)
可以发现，这里的情况就类似于递归，假设这个函数叫做 \(E(x)\)（\(x\) 表示目前剩余的蛇的数量，那么可以知道 \(E(x)= \lnot E(x - 1), E(2) =1\)。如果这样吃下去有一条蛇可以做到吃了不变成最弱的蛇，那么递归就到此为止（因为吃了不会变成最弱的话，吃不吃的选择不会由递归下去的结果决定，而是绝对的 \(1\)）。
由此可以将吃的阶段划分成为两部分：
-
最强的蛇吃了最弱的蛇不会变成最弱的蛇，一直这样吃下去
-
递归确认当前蛇是否应该吃掉最弱的蛇
会发现第一阶段结束过后第二阶段最多只会进行一次（顶多选择吃掉一次，第二条蛇肯定是不敢吃的）。
每次模拟都需要知道当前最强的蛇和最弱的蛇是谁，所以可以用 set 维护一下就可以了，时间复杂度为 \(\mathcal O(Tn\log n)\)，理论上可以拿 70pts。不过如果开了 O2 可以直接卡着脖子 AC。
#include<bits/stdc++.h>
using namespace std;
constexpr int _SIZE = 1e6;
int n, a[_SIZE + 5], T, k;
set<pair<int, int>> s;
void solve() {
s.clear();
for (int i = 1; i <= n; i++) s.insert(make_pair(a[i], i));
bool type = 0;
int flag, ans;
while (s.size() >= 2) { // 为了写着方便就把两个阶段合并到一起写的，type=1 表示第一阶段，type=2 表示第二阶段
auto weaker = s.begin();
auto stronger = --s.end();
pair<int, int> temp = make_pair(stronger->first - weaker->first, stronger->second);
s.erase(weaker), s.erase(stronger);
s.insert(temp); flag += type;
if (!type && s.begin()->second == temp.second) type = 1, ans = s.size(), flag = 0;
if (type && s.begin()->second != temp.second) break;
}
cout << ans + (flag % 2 == 1) << '\n';
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> T;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
solve();
for (int times = 2; times <= T; times++) {
cin >> k;
for (int i = 1; i <= k; i++) {
static int x, v;
cin >> x >> v;
a[x] = v;
}
solve();
}
return 0;
}
考虑正解做法，发现 100pts 的数据规模里面写了一个保证数据不降排列，这就在暗示可以使用单调队列来维护最大值和最小值。
定义两个双端队列 \(q1,q2\)，内部元素单调不降，将最开始的序列存到 \(q1\) 里面去。可以发现，在第一阶段的时候，生成出来的新蛇一定都是不能添加到 \(q1\) 内的（会破坏单调性），但是每次生成出来的新蛇又是具有单调性的。也就是说，将生成出来的新蛇添加到 \(q2\) 中就可以了。每次找最弱的蛇的时候都是一定在 \(q1\) 内的，最强的蛇就是 \(q1,q2\) 队尾的较大者。如果生成出来的新蛇比 \(q1\) 中最小的还要小，那么就证明当前这条蛇变成了最弱的蛇，进入第二阶段。
进入第二阶段的时候，分 \(q1,q2\) 已经没有什么必要了，所以就按照归并排序的方式合并到一个单调队列 \(q\) 中，然后模拟上面第二阶段的操作即可。
时间复杂度为 \(\mathcal O(Tn)\)。
#include<bits/stdc++.h>
using namespace std;
constexpr int _SIZE = 1e6;
int n, k, T, a[_SIZE + 5];
void solve() {
deque<pair<int,int>> q1, q2;
for (int i = 1; i <= n; i++) q1.push_back(make_pair(a[i], i));
int ans = 0, flag = 0;
while (q1.size() + q2.size() >= 2) {
auto weaker = q1.front(); q1.pop_front();
auto stronger = q1.back();
if (!q2.empty() && q2.back() > q1.back()) {
stronger = q2.back(); q2.pop_back();
} else q1.pop_back();
pair<int, int> temp = make_pair(stronger.first - weaker.first, stronger.second);
if (temp > q1.front()) q2.push_front(temp);
else {
q1.push_front(temp);
break;
}
}
deque<pair<int, int>> q;
while (!q1.empty() && !q2.empty()) {
if (q1.front() < q2.front()) q.push_back(q1.front()), q1.pop_front();
else q.push_back(q2.front()), q2.pop_front();
}
while (!q1.empty()) q.push_back(q1.front()), q1.pop_front();
while (!q2.empty()) q.push_back(q2.front()), q2.pop_front();
ans = q.size(), flag = 0;
while (q.size() >= 2) {
auto weaker = q.front(); q.pop_front();
auto stronger = q.back(); q.pop_back();
auto temp = make_pair(stronger.first - weaker.first, stronger.second);
flag++;
if (!q.empty() && temp < q.front()) q.push_front(temp);
else break;
}
cout << ans + (flag % 2 == 1) << '\n';
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> T;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
solve();
for (int i = 2; i <= T; i++) {
cin >> k;
for (int j = 1; j <= k; j++) {
static int x, y;
cin >> x >> y;
a[x] = y;
} solve();
}
return 0;
}