题解 P7078 【贪吃蛇（洛谷民间数据）】
OMG_wc
2020-11-11 04:27:50
~~比赛里能做出这题的人真的非常厉害，至少他的智商和蛇一样足够聪明~~。
首先有一个结论：
当前最强的蛇吃了最弱的蛇之后，如果没有变成最弱的蛇，他一定会选择吃！
证明：
假设当前最强的蛇叫石老板。
- 如果下一条最强的蛇如果依旧是石老板，那肯定不吃白不吃；
- 如果下一条最强蛇不是石老板，此时最强的蛇没有原先强，最弱的蛇也没原先弱，吃掉后肯定比石老板要弱。也就是说，当前最强的蛇吃了之后，如果会死，也会死在石老板前面。那么这样一来，这条蛇会想尽办法不死，从而石老板也一定能不死。
有了这个结论，一部分蛇可以放心大胆地吃了，但是问题来了，如果吃了之后变成最弱的蛇了，到底选择吃不吃呢？
稍微往后推一推就明白了：
当前最强蛇记为石老板，下一条最强蛇记为喵老板。石老板进食后变成最弱的蛇了，如果喵老板进食后不是最弱的蛇，他就会选择吃（根据开头的结论），这样石老板就凉了，所以石老板当初的选择一定是不吃。
如果喵老板进食后依旧是最弱的蛇，那就会考虑下一条最强蛇的情况，起名为汪老板。同样分两种情况：如果汪老板进食后不是最弱的蛇，那他就会选择吃，这样喵老板就凉了，所以他当初会选择不吃，这样石老板就不会死，那么石老板当初就会选择吃。如果汪老板进食后变成了最弱的蛇，那就再考虑下一条蛇………………
这个问题就变成了一个递归的问题了，直到**某条蛇吃了之后不是最弱的蛇或者只能下两条蛇为止**。这样，最后一条蛇会选择吃，倒数第二条蛇为了保命会选择不吃，倒数第三条蛇可以放心大胆的吃，倒数第四条蛇会保命选择不吃，倒数第五条蛇可以放心吃………………
这样，石老板选择吃不吃，就和最后一条蛇之间的奇偶性相关了。并且石老板选择不吃，游戏结束，石老板选择吃，游戏也会在下一轮结束（因为喵老板会选择不吃）。
到目前为止，这个题目很清晰了，只需模拟两个阶段即可：
阶段一：所有最强蛇进食后都不是最弱蛇，放心大胆吃！
阶段二：所有最强蛇进食后都是最弱蛇，直到有条蛇可以放心吃为止（吃了后不是最弱或者只剩两条）
阶段一结束时，游戏就基本结束了（根据阶段二的奇偶性看能不能再吃一次）
利用`set`可以方便地维护最强、最弱蛇，时间复杂度 $O(Tn\log n)$，只能拿 70 分，代码如下：
```c++
int a[N];
int main() {
int _;
scanf("%d", &_);
int n;
for (int cas = 1; cas <= _; cas++) {
if (cas == 1) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
} else {
int k;
scanf("%d", &k);
while (k--) {
int x, y;
scanf("%d%d", &x, &y);
a[x] = y;
}
}
set<pair<int, int> > se;
for (int i = 1; i <= n; i++) {
se.insert({a[i], i});
}
int flag = 0, ans;
while (1) {
if (se.size() == 2) {
se.erase(se.begin());
if (flag) {
if ((flag - se.size()) % 2) {
ans = flag + 1;
} else {
ans = flag;
}
} else
ans = 1;
break;
}
set<pair<int, int> >::iterator it = se.end();
it--;
int x = it->first, id = it->second;
int y = se.begin()->first;
se.erase(it);
se.erase(se.begin());
se.insert({x - y, id});
if (se.begin()->second != id) {
if (flag) {
if ((flag - se.size()) % 2) {
ans = flag + 1;
} else {
ans = flag;
}
break;
}
} else {
if (flag == 0) flag = se.size();
}
}
printf("%d\n", ans);
}
return 0;
}
```
正解：用两个双端队列 $q_1,q_2$ 维护即可。
先把初始的有序蛇放进 $q_1$ 里，此时 $q_1$ 已满足单调性，头部小，尾部大，我们后面会让 $q_2$ 也满足这样的单调性。
##### 第一阶段：
每次从 $q_1,q_2$ 的尾部取出最强的蛇，从 $q_1$ 头部取出最弱的蛇，如果吃了以后是最弱的，那就进入第二阶段，否则直接装入 $q_2$ 的头部。
为什么可以装进 $q_2$ 并且是 $q_2$ 里最弱的？其实证明最初的结论时已经解释过了，后面进食的蛇肯定是越来越弱的，而且这个阶段最弱的蛇一定在 $q_1$ 中。
##### 第二阶段：
此时最弱的蛇，就没必要丢进队列里了，单独维护一下就好了，因为连续的一段进食后都是最弱的，直到总蛇数等于 $2$ 或者进食后不是最弱为止，而最强的依旧从 $q_1,q_2$ 的尾部找。
这样就不需要用其他带 $\log$ 的数据结构维护了，时间复杂度 $O(Tn)$，代码如下：
```c++
int a[N];
int main() {
int _;
scanf("%d", &_);
int n;
for (int cas = 1; cas <= _; cas++) {
if (cas == 1) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
} else {
int k;
scanf("%d", &k);
while (k--) {
int x, y;
scanf("%d%d", &x, &y);
a[x] = y;
}
}
deque<pair<int, int> > q1, q2;
for (int i = 1; i <= n; i++) {
q1.push_back({a[i], i});
}
int ans;
while (1) {
if (q1.size() + q2.size() == 2) {
ans = 1;
break;
}
int x, id, y;
y = q1.front().first, q1.pop_front();
if (q2.empty() || !q1.empty() && q1.back() > q2.back()) {
x = q1.back().first, id = q1.back().second, q1.pop_back();
} else {
x = q2.back().first, id = q2.back().second, q2.pop_back();
}
pair<int, int> now = make_pair(x - y, id);
if (q1.empty() || q1.front() > now) {
ans = q1.size() + q2.size() + 2; // 不吃
int cnt = 0;
while (1) {
cnt++;
if (q1.size() + q2.size() + 1 == 2) {
if (cnt % 2 == 0) ans--;
break;
}
int x, id;
if (q2.empty() || !q1.empty() && q1.back() > q2.back()) {
x = q1.back().first, id = q1.back().second, q1.pop_back();
} else {
x = q2.back().first, id = q2.back().second, q2.pop_back();
}
now = {x - now.first, id};
if ((q1.empty() || now < q1.front()) && (q2.empty() || now < q2.front())) {
;
} else {
if (cnt % 2 == 0) ans--;
break;
}
}
break;
} else {
q2.push_front(now);
}
}
printf("%d\n", ans);
}
return 0;
}
```