自动搬运

查看原文

来自洛谷，原作者为

	metaphysis 故不积跬步，无以至千里；不积小流，无以成江海。——《荀子·劝学篇》

搬运于2025-08-24 22:31:20，当前版本为作者最后更新于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;
}