P4552 [Poetize6] IncDec Sequence

题目 P4552 [Poetize6] IncDec Sequence

题目描述 给定一个长度为 n的数列 a1,a2,…,an，每次可以选择一个区间[l,r]，使这个区间内的数都加 1 或者都减 1。

请问至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列有多少种。

输入格式 第一行一个正整数 n 接下来 n 行,每行一个整数,第 i+1行的整数表示 a_i 。

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

分析 昨天写了个前缀和，今天来道差分。 其实我之前都没写过差分的题目，不了解差分，今天学到了。

今天这题就是用差分来解决的。 取正数和负数中最大的是求出最少的步骤来得到一样的值 取正数和负数的差是看他两中间差几个数再加上本身，就是可能的情况了。

#include<bits/stdc++.h> using namespace std; typedef long long LL; int n, a[100005]; LL positive,negative, c[100005]; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); c[1] = a[1]; for (int i = 2; i <= n; i++) { c[i] = a[i]-a[i-1]; if (c[i] > 0) positive += c[i]; else negative -= c[i]; } printf("%lld\n%lld", max(positive, negative), abs(positive-negative)+1); return 0; }

(づ｡◕‿‿◕｡)づ