洛谷P10133 题解

一道差分黄题（但我似乎并没有用差分）

原题指路

题意简述

给定有 \(n\) 个元素的数组 \(a\)，

可以在任意位置 \(i\) 向后加上（或减去）一个首项为 1，公差为 1，长度为 \(n\) − \(i\) + 1（即结束点为 \(n\)）的等差数列。

问需要加（或减）几个等差数列可使 \(a\) 中的值全为 \(0\)。

思路解析

想了很久不知道怎么写，所以乱水一点。

从第一个元素开始向后遍历，依次将每个元素清零。

使用两个变量 \(flag\) 与 \(cs\)
\(flag\) 记录当前元素需要改变的值，\(cs\) 记录 \(flag\) 需要改变的值。

对于第 \(i\) 个元素而言，先将它改变 \(flag\)，之后通过当前元素的值改变 \(cs\) 的值，然后改变 \(flag\) 的值。

代码展示

#include<bits/stdc++.h>
#define int long longusing namespace std;const int N = 2e5 + 100;
int n, a[N], ans, flag, cs;signed main(){freopen("bact.in", "r", stdin);freopen("bact.out", "w", stdout);scanf("%lld", &n);for(int i = 1; i <= n; i++){scanf("%lld", &a[i]);}for(int i = 1; i <= n; i++){flag += cs;a[i] += flag;if(a[i] == 0) continue;flag += (a[i] * -1);ans += abs(a[i]);cs += (a[i] * -1);}printf("%lld", ans);return 0;
}