P7078 [CSP-S2020] 贪吃蛇

P7078 [CSP-S2020] 贪吃蛇

草原上有 \(n\) 条蛇，编号分别为 \(1, 2, \ldots , n\)。初始时每条蛇有一个体力值 \(a_i\)，我们称编号为 \(x\) 的蛇实力比编号为 \(y\) 的蛇强当且仅当它们当前的体力值满足 \(a_x > a_y\)，或者 \(a_x = a_y\) 且 \(x > y\)。

接下来这些蛇将进行决斗，决斗将持续若干轮，每一轮实力最强的蛇拥有选择权，可以选择吃或者不吃掉实力最弱的蛇：

1. 如果选择吃，那么实力最强的蛇的体力值将减去实力最弱的蛇的体力值，实力最弱的蛇被吃掉，退出接下来的决斗。之后开始下一轮决斗。
2. 如果选择不吃，决斗立刻结束。

每条蛇希望在自己不被吃的前提下在决斗中尽可能多吃别的蛇（显然，蛇不会选择吃自己）。

现在假设每条蛇都足够聪明，请你求出决斗结束后会剩几条蛇。

本题有多组数据，对于第一组数据，每条蛇体力会全部由输入给出，之后的每一组数据，会相对于上一组的数据，修改一部分蛇的体力作为新的输入。

• 对于 \(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\) 以不降顺序排列。

我们先证明一个至关重要的结论：

引理

如果最强的蛇吃完后不会成为最弱者，那么必须吃！

证明

• 如果吃了之后还是最强蛇，那么主动权依旧在手上，显然要吃。
• 否则，由于次弱的蛇比最弱的蛇强，次强的蛇比最强的弱，因此次强的吃了次弱的，实力不如自己，而次强的一定会想尽办法活下来，因此自己也能活下来，所以吃了肯定没事。 当然，如果只剩两条蛇，那当然得吃！

如果吃了之后成了最弱蛇，我们也推一下：

假设A吃了，次强的是B，那就要看B能不能吃A，这就类似递归了，如果出现引理的情况，那么倒数第一条不能吃（因为下一条一定会吃他），倒数第二条就会吃（因为下一条不吃他），以此类推，我们发现，只用判断自己是倒数第几条就行了。

那么就是两个阶段：

1. 吃了不是最弱的，放心大胆吃！
2. 吃了变成了最弱的，我们按照上面的过程模拟（不需要真的递归），这一过程是最后一步，因为自己如果吃了，下一条是奇数局面，它不吃。

考虑模拟这个过程，用 set 是 \(O(n \log n)\) 的，有 70pts，考虑加速。

类似蚯蚓和合并果子（加强版）这两题，我们可以用两个单调递增的队列 \(q_1\) 和 \(q_2\) 维护，一开始全放在 \(q_1\)，吃了之后不是最弱的就放 \(q_2\) 队首，吃了成了最弱的就单开变量维护，根据上面的引理易知单调性成立。

然后就 \(O(n)\) 过了。

实现

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
typedef pair<int, int> pii;
int a[MAXN], n, ans, x, id, y;
list<pii> q1, q2;
pii now;
bool chk() // 模拟二阶段判断能不能吃
{
    int cnt = 0; // 二阶段进行的局数
    while (1)
    {
        cnt++;                          // 安全！
        if (q1.size() + q2.size() == 1) // 吃完了，结束
            break;
        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()))) // 下一条蛇安全，那么自己就会被吃，退出
            break;
    }
    // cnt 是奇数，危险！
    return !(cnt & 1);
}
void solve()
{
    q1.clear(), q2.clear();
    for (int i = 1; i <= n; i++)
        q1.push_back({a[i], i});
    while (1)
    {
        if (q1.size() + q2.size() == 2) // 剩俩蛇
        {
            ans = 1;
            break;
        }
        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();
        now = {x - y, id};                  // 吃！
        if (q1.empty() || q1.front() > now) // 自己变成最弱的了，进入二阶段
        {
            ans = q1.size() + q2.size() + 2 - chk();
            break;
        }
        else // 安全！
            q2.push_front(now);
    }
    cout << ans << endl;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    for (int tid = 1, k, x, y; tid <= T; tid++)
    {
        if (tid == 1)
        {
            cin >> n;
            for (int i = 1; i <= n; i++)
                cin >> a[i];
        }
        else
        {
            cin >> k;
            while (k--)
            {
                cin >> x >> y;
                a[x] = y;
            }
        }
        solve();
    }
    return 0;
}