题解：CF2053I1 Affectionate Arrays (Easy Version)

Daniel1234 · 2025-01-03 23:18:13 · 题解

写篇题解记录一下考场思路。

思路

首先我们发现将折线图画出来，一定是一条起点为 (0,0)，而终点为 (n, sum) 的折线。

所以猜测最终所有前缀都在 0 \sim sum 之间。

从前往后考虑每一位，记录当前前缀，当前插入次数，维护的话就是加入 a_{i+1}，看有没有超出 [0,sum]，超出的话答案加 1，当前前缀变为超出边界。

然后测样例，发现假完了，于是我们想到可以记录 l,r，表示当前所有可行前缀中的最小可能值和最大可能值。

转移的话注意需要插入时插入的数不能爆出边界。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int T, n;
int a[3000005];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> T;
    while(T--){
        cin >> n;
        int sum = 0;
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            sum += a[i];
        }
        int ans = 0;
        int l = 0, r = 0;
        for(int i = 1; i <= n; i++){
            int pl = l, pr = r;
            l += a[i], r += a[i];
            if(l < 0)l = 0;
            if(r > sum)r = sum;
            if(l > r){
                ans++;
                l = max(0ll, a[i]), r = min(sum, sum + a[i]);
            }
        }
        ans += r < sum;
        ans += n;
        cout << ans << '\n';
    }
    return 0;
}