回旋加速器（2021 CoE-II C）

metaphysis · 2021-03-07 10:39:08 · 题解

朴素的做法就是从每一个加速腔开始，遍历整个环形管道，然后找出最后剩余动能最大的加速腔，这是 O(n^2) 的方法。

如果认真加以思考，本题与求最大连续子数组和相似。在任何一个加速腔，我们只关心动能的损耗，定义 add[i] 为第 i 个加速腔能够为质子束提供的动能，loss[i] 为从第 i 个加速腔运行到第 i + 1 个加速腔时所损耗的动能，进一步定义：

那么这道题目包含两个问题：（1）能否在环上绕一圈？（2）如果能，这个加速腔在那里？

第一个问题很简单，对 diff 数组做个加和就好了，energy = \sum diff[i]，如果最后 energy 是非负值，那么肯定存在这样的一个加速腔。如果是负值，动能的损耗大于动能的供给，不可能有解。得到第一个问题的答案只需 O(n)。

对于第二个问题，起始加速腔在哪里？假设我们从环上取一个区间 [i,j],j \gt i，然后对于这个区间的 diff 加和，定义

如果 sum[i, j] 小于 0，那么这个加速腔肯定不会在 [i, j] 这个区间里，跟第一个问题的道理相似。例如，假设 i 是 [1, n] 的解，那么我们知道任意 sum[k, i-1](1 \le k \lt i-1) 肯定是小于 0，否则解就应该是 k。同理，sum[i, n] 一定是非负的，否则，解就不应该是 i，而是 i 和 n 之间的某个加速腔。所以第二个问题的答案就是在 1 到 n 之间找到加和为非负值的第一个连续子序列，注意，这个连续子序列的结尾必然是 n。

参考代码：

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 10;
int n, ei[MAXN], di[MAXN], diff[MAXN];

int main(int argc, char *argv[])
{
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    int cases;
    cin >> cases;
    for (int cs = 1; cs <= cases; cs++)
    {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> ei[i];
        for (int i = 0; i < n; i++) cin >> di[i];
        for (int i = 0; i < n; i++) diff[i] = ei[i] - di[i];

        int energy = 0, sum = 0, idx = 0;
        for (int i = 0; i < n; i++)
        {
            energy += diff[i];
            sum += diff[i];
            if (sum < 0)
            {
                idx = i + 1;
                sum = 0;
            }
        }
        if (energy < 0) cout << "Failed!\n";
        else cout << (idx + 1) << '\n';
    }
    return 0;
}