今日学习记录
1. P4552 [Poetize6] IncDec Sequence - 洛谷
关键词：差分
问题分析：
给定一个长度为 n 的数列 a1,a2,⋯,an，每次可以选择一个区间[l,r]，使这个区间内的数都加 1 或者都减 1。
请问至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列有多少种。
核心思路:
差分
**最终代码：
#include<bits/stdc++.h>
using namespace std;
int n;
typedef long long ll;
int main(){
cin>>n;
vector<ll> arr(n+1,0);
for(int i = 1;i<=n;i++){
cin>>arr[i];
}
ll q = 0,p = 0;
for(int i = 1;i<n;i++){
ll c = arr[i+1]-arr[i];
if(c>0) q += c;
else p -= c;
}
cout<<min(p,q)+abs(p-q)<<endl;
cout<<abs(p-q)+1;
return 0;
}学到的点：
- 差分