codevs 2498 IncDec Sequence （差分数组）

codevs 2498 IncDec Sequence （差分数组）

Description

给定一个长度为 n 的数列 {a1,a2…an} ，每次可以选择一个区间 [l,r] ，使这个区间内的数都加一或者都减一。问至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列有多少种。

Input

第一行一个正整数 n接下来 n 行，每行一个整数，第 i+1 行的整数表示 ai 。

Output

第一行输出最少操作次数第二行输出最终能得到多少种结果

Sample Input

41122

Sample Output

12

思路

差分数组，我们令 d d 为 aa 的差分数组，则对区间 ​​[l,r]​​​ 加 c c 的操作即可转化为 ​​​d[l]+c, d[r+1]-c​​ 这两步。

令 s1s1 代表差分数组中除 d0 d 0 以外的正数和，s2 s 2 代表差分数组中除 d0 d 0

因为 c c 的大小为 +1+1 或者 −1 − 1 ，我们想要把除 d0 d 0 以外的其他元素（d1…dn−1 d 1 … d n − 1 ）全部调整为 0 0 显然需要 max(s1,s2)max(s1,s2) 步操作（多余的那些操作可以附加到 d0 d 0 或者 dn d n

于是，原数列的值便全部与 d0 d 0 相等了，第二问即 d0 d 0 的变化区间大小，因为我们说多余的操作可以附加到 d0 d 0 或者 dn d n 之中，其中 dn d n 已经超出了我们的判断范围，因此对它的操作是无意义的，可以忽略不计，则最终结果为 abs(s1−s2)+1 a b s ( s 1 − s 2 ) + 1

AC 代码

#include #define IO \ ios::sync_with_stdio(false); \ cin.tie(0); \ cout.tie(0);using namespace std;typedef long long LL;const int maxn = 1e5 + 10;int n;LL a[maxn];LL d[maxn];int main() {#ifdef LOCAL_IM0QIANQIAN freopen("test.in", "r", stdin); freopen("test.out", "w", stdout);#else IO;#endif // LOCAL_IM0QIANQIAN cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } LL s1 = 0, s2 = 0; d[0] = a[0]; for (int i = 1; i < n; i++) { d[i] = a[i] - a[i - 1]; if (d[i] > 0) s1 += d[i]; else if (d[i] < 0) s2 -= d[i]; } cout << max(s1, s2) << endl; cout << abs(s1 - s2) + 1 << endl; return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。