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

Nostopathy · 2026-05-09 20:51:52 · 题解

轻松获得截至发布的最优解 99\text{ms}，领先第二名 34\text{ms}。

看到得到 e_i 动能，损失 d_i 动能，可以将其简化为获得 a_i=e_i-d_i 动能。由于是环形，将数组复制一遍。

那么这个问题转化为寻找是否有子段 a_l,a_{l+1},\dots,a_{l+n-1}，满足 \forall x \in \{1, 2, \dots, n\}, \sum_{i=1}^{x} a_i \ge 0，即任意前缀子段的和都非负。

为什么这样说？当走到某处动能为 0 便无法前进，从原来选定的开头走过来就无法走出长度 \ge n，需要新开一段。条件保证了可以在动能非负情况下走到每个点。

我们使用变量记录一下当前段的开头、总和、长度，可以 \Theta(n) 地求出答案。

#include <bits/stdc++.h>
using namespace std;

inline int read()
{
    int x=0,f=1;
    char ch=getchar_unlocked();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar_unlocked();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar_unlocked();
    return x*f;
}

const int N = 2e6 + 5;

int n, e[N], d[N];

void solve(){
    n = read();
    for(int i = 1; i <= n; ++ i)
        e[i] = read();
    for(int i = 1; i <= n; ++ i)
        d[i + n] = d[i] = e[i] - read();
    int s = 1, sum = 0, cnt = 0;
    for(int i = 1; i <= 2 * n; ++ i){
        sum += d[i];
        if(sum < 0){
            s = i + 1;
            cnt = 0;
            sum = 0;
            continue;
        }
        ++ cnt;
        if(cnt == n){
            printf("%d\n", s);
            return;
        }
    }
    printf("Failed!\n");
}

signed main(){
    int t = read();
    while(t --)
        solve();

    return 0;
}