本題考察的是差分的思想。
設 b[i]=a[i]-a[i-1]
因為我們要想讓其所有的數字都相等。故即b[2],b[3].......b[n]都得為0才行。
此時數組所有的數的值都是b[1]。
因為我們的差分操作是每次選兩值，讓其一個加1，一個減1，基于貪心的思想正負數相互結合。
剩下的即為同符號的數。
設b[2]…b[n]中正數的和為sum1,負數的和為sum2
故最少的操作次數就是max( sum1, abs(sum2) )
那么結果的種類為，其實結果的種類就是b[1]的取值有多少個，可以得出有abs(sum1)-abs(sum2)種情況再加上b[1]不變本身的這種情況
故一共有abs(abs(sum1)-abs(sum2))+1種.

舉一個最簡單的例子。假如上面的正負數結合后還有一個正數3未解決。
那么可以 b[1]不變，讓3和 b[n+1]結合
可以讓b[1]變1次，讓2和 b[n+1]結合
可以讓b[1]變2次，讓1和 b[n+1]結
可以讓b[1]變3次，讓0和 b[n+1]結
故b[1]一共有四種結果

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; typedef long long int LL; LL a[N],b[N],n; LL sum1,sum2; int main(void) {cin>>n;for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i]-a[i-1];for(int i=2;i<=n;i++)if(b[i]>=0) sum1+=b[i];else sum2+=b[i];cout<<max(sum1,abs(sum2))<<endl;cout<<abs(abs(sum1)-abs(sum2))+1<<endl;return 0; }

總結

以上是生活随笔為你收集整理的100. 增减序列【差分 / 思维】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。