Songhn Blog

BZOJ3043 IncDec Sequence

 ACM

题意简述：

给定一个长度为$n$的数列$a1,a2,\cdots ,an$,每次可以选择一个区间$[l,r]$,使下标在这个区间内的数都加一或者都减一,求至少需要多少次操作才能使数列中的所有数都一样

输入格式:

第一行输入正整数$n$,接下来$n$行，每行输入一个整数,第$i+1$行的整数代表$a_{i}$

输出格式:

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

数据范围:

$0\lt n\leq10^{5},0\leq a_{i}\lt 2147483648$

题解:

首先本题的主要思想是差分+贪心

要让所有数都一样也就是让该数列的差分数列$a$除$a_{1}$以外都为0。而选择区间$[l,r]$加在差分数列中就表现为$a_{l} +1$与$a_{r+1} -1$,减一同理

而我们对区间$[i,j-1]$的操作$i,j$可能有四种情况

  1. $2\leq i,j\leq n$

  2. $i=1,2\leq j\leq n$

  3. $2\leq i\leq n,j=n+1$

  4. $i=1,j=n+1$

其中不难发现4是无用操作,而2,3等价,由贪心的思想可以发现应该优先使用1操作之后再用2,3操作,而1操作应该满足这样的条件:$i$为负,$j$为正,所以操作1可用的总次数即为$min(t1,t2)$($t1$为所有正数的和,$t2$为所有负数的绝对值的和),之后剩下的$abs(t1-t2)$ 可以任意用操作2,3,这样最少操作次数即为$min(t1,t2)+abs(t1-t2)$,而操作可能数由于剩下的可以任选操作2或3,所以即为$abs(t1+t2)+1$

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn = 100050;
int n,a[maxn];
ll t1,t2;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=n;i>=1;i--) a[i]-=a[i-1];
	for(int i=2;i<=n;i++) 
	if(a[i]>0) t1+=a[i];
	else t2-=a[i];
	printf("%lld\n",min(t1,t2)+abs(t1-t2));
	printf("%lld\n",abs(t1-t2)+1);
	return 0;
}

相关文章：