BZOJ 3043 IncDec Sequence：反向差分

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3043

题意：

　　给定一个长度为n的数列a[i]，每次可以选择一个区间[l,r]，使这个区间内的数都加一或者都减一。

　　求：（1）至少需要多少次操作才能使数列中的所有数都一样。

　　　　（2）在保证最少次数的前提下，最终得到的数列有多少种。

题解：

　　对于差分来说，给[l,r]+1（或-1）就是给差分数组s[l]+1和s[r+1]-1。

　　所以数列a[i]，是从一个所有元素都相等的初始数组，经过若干次差分操作得来的。

　　因此可以求出a[i]的差分数组s[i]。

　　因为要使操作次数最小，所以先让s[i]中的正数和负数配对（可能有剩余），每一对"+1"和"-1"对应一次操作。

　　剩下来的正数（或负数），只能单独消去。

　　pos为s[i]的正数之和，neg为s[i]的负数的绝对值之和。

　　所以第（1）问的答案为max(pos,neg)。

　　因为要使操作次数最小，所以配对的"+1"和"-1"一定会被消去，对于最终数列的种类没有影响。

　　所以只用考虑剩下来的正数（或负数）的消去方法。

　　对于一个在i位置的"+1"来说，有两种消去方法：

　　　　（1）自己跟自己消，即在s[i]再-1。

　　　　　　从效果上看，相当于给a[i]及后面的数都-1。

　　　　（2）跟位置1消，即在s[i]处-1。

　　　　　　相当于给[1,i]之间的数-1。

　　对于这两种消去方法，最终数组的数字大小相差1。

　　剩下的数共有abs(pos-neg)个。

　　所以最终数组的数字大小最多相差abs(pos-neg)，即数字种类有abs(pos-neg)+1种。

　　abs(pos-neg)+1即为第（2）问答案。

AC Code:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #define MAX_N 100005

 using namespace std;

 int n;

 long long pos=;

 long long neg=;

 long long a[MAX_N];

 long long labs(long long x)

 {

     return x>?x:-x;

 }

 void read()

 {

     cin>>n;

     for(int i=;i<n;i++)

     {

         cin>>a[i];

     }

 }

 void solve()

 {

     for(int i=;i<n;i++)

     {

         if(a[i]>a[i-]) pos+=a[i]-a[i-];

         else neg+=a[i-]-a[i];

     }

 }

 void print()

 {

     cout<<max(pos,neg)<<endl;

     cout<<labs(pos-neg)+<<endl;

 }

 int main()

 {

     read();

     solve();

     print();

 }

巴特西

BZOJ 3043 IncDec Sequence：反向差分

最新文章

热门文章