「BZOJ3043」IncDec Sequence

2014年11月23日3,7390

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

题解

设差分序列为d

要使得整个序列相同，即d[i]=0(2≤i≤n)

题目相当于允许将d序列某个值+1，某个值-1

设∑ d[i] (2≤i≤n&&d[i]≥0) = a

∑ d[i] (2≤i≤n&&d[i]≤0) = b

显然第一问答案是max(a,b)。。。

将负数和正数配对消去后。。。剩下的abs(a-b)次操作可以配对给d[n+1]/d[1]

所以d[1]最终取值abs(a,b)+1种

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll ans1,ans2;
int n;
int a[100005];
int main()
{
	n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=2;i<=n;i++)
		if(a[i]>a[i-1])ans1+=a[i]-a[i-1];
		else ans2+=a[i-1]-a[i];
	printf("%lld\n%d",max(ans1,ans2),abs(ans1-ans2)+1);
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

ll ans1,ans2;

int n;

int a[100005];

int main()

{

n=read();

for(int i=1;i<=n;i++)a[i]=read();

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

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

else ans2+=a[i-1]-a[i];

printf("%lld\n%d",max(ans1,ans2),abs(ans1-ans2)+1);

return 0;

}

« 「BZOJ1557」GC转移「BZOJ3252」攻略 »

hzwer.com _ Home | http://hzwer.com

「BZOJ3043」IncDec Sequence

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论