【BZOJ2792】[Poi2012]Well

Description

给出n个正整数X1,X2,...Xn，可以进行不超过m次操作，每次操作选择一个非零的Xi，并将它减一。

最终要求存在某个k满足Xk=0，并且z=max{|Xi - Xi+1|}最小。

输出最小的z和此时最小的k。

Input

第一行两个正整数n, m (1<=n<=1,000,000, 1<=m<=10^18)。第二行n个正整数X1,X2,...Xn (Xi<=10^9)。

Output

输出k和z。数据保证方案一定存在。

Sample Input

16 15
8 7 6 5 5 5 5 5 6 6 7 8 9 7 5 5

Sample Output

1 2

HINT

将X序列变为

0 2 4 5 5 5 5 5 6 6 7 8 9 7 5 5

此时k=1，z=2，共操作了8+5+2=15次。

题解：容易想到二分答案，但是如何判定是个问题。我们先不考虑xk=0的要求，我们先正着反着扫两遍序列，将相邻两项差>mid的改掉，即可满足任意相邻的两项差都不超过mid。

然后我们枚举k，看一下如果xk=0会对那些数产生影响。如果xk=0，那么k左右两边的数就会形成两个公差为mid的等差数列向外延伸，一直延伸到该位置的数比等差数列对应的数要小为止。所以每个数的影响范围都是一段区间[l,r]，并且容易发现k越大l越大，k越小r越小。所以我们可以用双指针处理出每个数影响区间的左端点和右端点，最后扫一遍得到最小的k即可。

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

typedef long long ll;

const int maxn=1000010;

int n,ans;

int v[maxn],x[maxn],ls[maxn],rs[maxn];

ll m;

ll s[maxn],s1[maxn],s2[maxn];

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

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

	while(gc>='0'&&gc<='9')	ret=ret*10+(gc^'0'),gc=getchar();

	return ret*f;

}

inline bool check(int mid)

{

	ll i,j,sum=0;

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

	{

		v[i]=x[i];

		if(i>1)	v[i]=min(v[i],v[i-1]+mid);

	}

	for(i=n-1;i>=1;i--)	v[i]=min(v[i],v[i+1]+mid);

	s1[n+1]=s2[0]=1ll<<60;

	for(i=1;i<=n;i++)	s[i]=s[i-1]+v[i],sum+=x[i]-v[i],s2[i]=min(s2[i-1],v[i]-i*mid);

	for(i=n;i>=1;i--)	s1[i]=min(s1[i+1],v[i]+i*mid);

	for(i=j=1;i<=n;i++)

	{

		for(;s1[j]<i*mid;j++);

		ls[i]=j;

	}

	for(i=j=n;i>=1;i--)

	{

		for(;s2[j]<-i*mid;j--);

		rs[i]=j;

	}

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

	{

		if(sum+s[rs[i]]-s[ls[i]-1]-mid*(i-ls[i])*(i-ls[i]+1)/2-mid*(rs[i]-i)*(rs[i]-i+1)/2<=m)

		{

			ans=i;

			return 1;

		}

	}

	return 0;

}

int main()

{

	n=rd(),scanf("%lld",&m);

	int i,l=0,r=0,mid;

	for(i=1;i<=n;i++)	x[i]=rd(),r=max(r,x[i]);

	check(2);

	while(l<r)

	{

		mid=(l+r)>>1;

		if(check(mid))	r=mid;

		else	l=mid+1;

	}

	printf("%d %d",ans,r);

	return 0;

}

巴特西

【BZOJ2792】[Poi2012]Well 二分+双指针法