題目鏈接：點擊查看

題目大意：給定一個長度為 n(n≤10^5 ) 的數(shù)列 {a_1,a_2,…,a_n}，每次可以選擇一個區(qū)間 [l,r]，使下標在這個區(qū)間內(nèi)的數(shù)都加一或者都減一。求至少需要多少次操作才能使數(shù)列中的所有數(shù)都一樣，并求出在保證最少次數(shù)的前提下，最終得到的數(shù)列可能有多少種。

題目分析：雖然是看過大藍書之后再來做這個題的，但還是有一些細節(jié)沒有想明白，想了好半天才算是消化了這個題目，真的是一道質(zhì)量很好的差分，對于這個題目而言，我們想要用最少的操作數(shù)讓最后的數(shù)列都變?yōu)橐粋€相同的數(shù)字，我們可以先統(tǒng)計一下一開始相鄰兩個數(shù)字之間的差（區(qū)分正負），因為是可以區(qū)間操作的，普通的差分是b[l]+=,b[r+1]--，所以我們貪心的策略，首先匹配正負不同的，也就是正負可以相互抵消，我們設(shè)pos儲存的是正數(shù)的和，neg儲存的是負數(shù)的絕對值之和，那么就有min(neg,pos)的正數(shù)和負數(shù)可以互相抵消，現(xiàn)在還剩下了abs(neg-pos)的正數(shù)或負數(shù)無法兩兩抵消，那么我們可以將其與左右兩端的兩個邊界相互匹配，一共是需要匹配abs(neg-pos)次，這樣第一個答案就是min(nge,pos)+abs(neg-pos)=max(neg,pos)，因為主要最后答案的差別是出在最后全正或全負的值與端點匹配的過程中，所以一共能組成不同的方案也是有abs(neg-pos)+1種，也就是第二問的答案了，相信對于第一問的最小值肯定沒有什么疑問了，主要是第二問的abs(neg-pos)+1還是比較難想的，換種表達方式吧，假如現(xiàn)在我們剩下了k=abs(neg-pos)+1的正數(shù)，這是一個什么概念？當(dāng)前序列要么是一個非嚴格遞增的序列，要么是一個非嚴格遞減的序列，那么我們的答案就可以在這個區(qū)間內(nèi)浮動，也就是0~abs(neg-pos)中一共有abs(neg-pos)+1個數(shù)，都可以當(dāng)做最終的答案

舉個很簡單的例子來理解一下吧：

1 3 5 3

差分后的答案為(從第二項開始處理，意思就是無視第一項)

1 2 2 -2

我們優(yōu)先匹配正負數(shù)，顯然一個-2匹配一個2，那么匹配完成后序列就變成了：

1 3 3 3(答案唯一)

這個時候的差分為：

1 2 0 0

我們現(xiàn)在的目標是要對于2這個點與左端點匹配或右端點匹配，現(xiàn)在有三種方案：

與右端點匹配兩次，每次都減一，得到的差分為1 0 0 0，答案序列為1 1 1 1

與左端點匹配一次，加一，與右端點匹配一次，減一，得到的差分為2 0 0 0，答案序列為2 2 2 2

與左端點匹配兩次，每次都加一，得到的差分為3 0 0 0，答案序列為3 3 3 3

大概就是這么個意思了，還是需要多多琢磨啊，這個題目的代碼很簡單，但是思維卻很復(fù)雜

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int a[N];int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n;scanf("%d",&n);LL p=0,q=0;//q:維護負數(shù)的權(quán)值和的絕對值，p:維護正數(shù)的權(quán)值和for(int i=1;i<=n;i++)scanf("%d",a+i);for(int i=2;i<=n;i++)if(a[i]-a[i-1]>0)p+=a[i]-a[i-1];elseq+=a[i-1]-a[i];cout<<max(p,q)<<endl<<llabs(p-q)+1<<endl;return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CH - 0304 IncDec Sequence(差分+思维)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。