首页 > 代码库 > BZOJ3043: IncDec Sequence

BZOJ3043: IncDec Sequence

3043: IncDec Sequence

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 233  Solved: 132
[Submit][Status]

Description

给定一个长度为n的数列{a1,a2...an},每次可以选择一个区间[l,r],使这个区间内的数都加一或者都减一。
问至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列有多少种。

Input

第一行一个正整数n 
接下来n行,每行一个整数,第i+1行的整数表示ai。

Output

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

Sample Input

4
1
1
2
2

Sample Output


1
2

HINT

 

对于100%的数据,n=100000,0<=ai<2147483648

 

Source

Poetize6

题解:
为何我想到了差分序列还是没有想到构造解T_T我还以为我想复杂了。。。
出题人:

对于带有“将一段区间内的每个数全部加上某个值”这种操作的题目,通常考虑差分原数列以简化情况,将对一段区间的操作转化为对某两个特定数的操作。

我们定义d_1 = a_1, d_i = a_i - a_{i-1} ( 2 ≤ i ≤ n ), d_{n+1} = 0(事实上,稍后我们会看到d_1和d_{n+1}的值并不重要),,可以发现,原题中的“将[l,r]内的数都加一或都减一”将对应“将d_l + 1,将d_{r+1} - 1”(或反之)的操作。

显然,题目中要求的a数列中的所有数全部相等的条件等同于使d_i = 0 ( 2 ≤ i ≤ n ),最后数列中的数即为d_1,而题目中的操作允许我们把d数列中的某个数+1,某个数-1。要将d数列中第二项至第n项全部变为0并使操作次数最少,首先我们将每个负数和每个正数配对执行操作,设d数列中第2至第n项所有正数分别求和得到的值为p,负数分别求和得到的值的*绝对值*为q,这一步的操作次数即为min{p,q}。此时还剩余和的绝对值为abs(p-q)的数没有变为0,每次操作我们可以将其与d_1或d_{n+1}配对进行操作,操作次数为abs(p-q),容易看出,最终d_1的可能取值有abs(p-q)+1种。因此,第一问的答案即为max{p,q},第二问的答案即为abs(p-q)+1。

 

再一次跪到了构造题上T_T

代码:

 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 1000000+10014 #define maxm 500+10015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define mod 100000000723 using namespace std;24 inline int read()25 {26     int x=0,f=1;char ch=getchar();27     while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();}28     while(ch>=0&&ch<=9){x=10*x+ch-0;ch=getchar();}29     return x*f;30 }31 ll n,a[2];32 int main()33 {34     freopen("input.txt","r",stdin);35     freopen("output.txt","w",stdout);36     n=read();int x=read(),y,z;37     for2(i,2,n)38     {39         y=read();z=y-x;40         a[z>=0?1:0]+=abs(z);41         x=y;42     }43     printf("%lld\n",max(a[0],a[1]));44     printf("%lld\n",abs(a[1]-a[0])+1);45     return 0;46 }
View Code

 

BZOJ3043: IncDec Sequence