P7078
Solution
首先观察一个回合，如果要吃，那一定是最大的吃最小的。
所以一定有一条蛇只要不是最小的就不会被吃。
那么看看多回合，可以发现操作顺序（每回合吃别人的蛇）一定是从大到小的，并且每回合被吃的一定是从小到大的。
那么在知道第 $i$ 轮被吃掉的一定是 $a_i$，那么停止的条件就很明显了，如果一条蛇吃了别人就会变成最小的，那就不能吃了。
所以停下来的条件就是最大的吃了变成最小的。
那么接下来看看怎么模拟：
- 取出数组和队列中最大的。
- 吃掉最小的。
- 如果触发停止条件，就判断最后一步吃不吃。
void solve() {
l = 1, r = n;//原数组中没有用过的
while (!q.empty()) q.pop();//队列存被吃了的。
while (l <= r) {
pair<LL, LL> x = {0, 0};
if (r > l) x = a[r];
if (!q.empty()) x = max(x, q.front());//在队列和数组中找到最大的一个
if(r-l<1) break;
if (a[r] == x) r--;//在数组中
else q.pop();//在队列中
x.first -= a[l].first;//吃。。。好吃
if (x < a[l + 1]) {//吃掉最小的，比现在最小的还小就退出
if (!check(x)) l++;//往后看
break;
}
q.push(x);
l++;
}
cout << n - l + 1 << '\n';
}但是我们发现在停止的时候有两种情况，这个最大的蛇到底能不能吃。
这个时候用一个函数判断一下最后一次吃不吃：
- 找到能吃的最小的一个。
- 和上面的步骤一样吃的。
- 看一下操作次数的奇偶。
bool check(pair<LL, LL> x) {
LL cnt = 1;
pair<LL, LL> last;
if (l < r) last = a[l + 1];
if (!q.empty()) last = min(last, q.back());//找到小的那个
while (true) {
pair<LL, LL> to = {0, 0};
if (l < r) to = a[r];
if (!q.empty()) to = max(to, q.front());
if (a[r] == to) r--;
else if (!q.empty()) q.pop();
to.first -= x.first;
if (last <= to) break;
x = to，cnt++;
}
return cnt % 2;
}我们发现如果这一次吃了，那么下一次一定不能吃，但是下一次不吃就可以下下次吃（这里可以手动模拟感性了解一下），所以判断一下后面的操作次数，如果是偶数，那么就最后一次的时候可以吃。
代码就不放了，把上面两个拼起来就好了。