【BZOJ3316】JC loves Mkk 分数规划+单调队列

【BZOJ3316】JC loves Mkk

Description

Input

第1行，包含三个整数。n，L，R。
第2行n个数，代表a[1..n]。

Output

仅1行，表示询问答案。
如果答案是整数，就输出整数；否则，输出既约分数“P/Q”来表示。

Sample Input

5 3 4
3 1 2 4 5

Sample Output

7/2
HINT
1≤L≤R≤n≤10^5，0≤ai≤10^9，保证问题有解,数据随机生成

题解：直接二分答案，然后每个糖果的权值都变成a[i]-mid，我们需要找到一段长度在[L,R]中的区间使得权值和>=0。然后我们将区间和转变成前缀相减的形式，所以只需要找到s[j]<s[i],j<i这样的i,j就行了。那么对于每个s[i]，我们肯定是贪心地选取前面最小的s[j]，这个用单调队列维护即可。

但是要求区间长度是偶数，所以我们需要开对奇偶各开一个单调队列。同时要求答案是分数，这个是需要再最后算一下就行了。

#include <cstdio>

#include <cstring>

#include <iostream>

typedef long long ll;

using namespace std;

const int maxn=100010;

int n,L,R,h1,t1,h2,t2;

ll ans1,ans2,g;

ll A[maxn<<1],S[maxn<<1];

double v[maxn<<1],s[maxn<<1];

int q1[maxn<<1],q2[maxn<<1];

ll gcd(ll a,ll b)

{

	return (!b)?a:gcd(b,a%b);

}

bool check(double x)

{

	int i;

	for(i=1;i<=n<<1;i++)	v[i]=A[i]-x,s[i]=s[i-1]+v[i];

	h1=h2=t1=1,t2=0,q1[1]=0;

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

	{

		while(h1<=t1&&q1[h1]<i-R)	h1++;

		while(h2<=t2&&q2[h2]<i-R)	h2++;

		if(!(i&1)&&h1<=t1&&s[q1[h1]]<=s[i])

		{

			ans1=S[i]-S[q1[h1]],ans2=i-q1[h1],g=gcd(ans1,ans2),ans1/=g,ans2/=g;

			return 1;

		}

		if((i&1)&&h2<=t2&&s[q2[h2]]<=s[i])

		{

			ans1=S[i]-S[q2[h2]],ans2=i-q2[h2],g=gcd(ans1,ans2),ans1/=g,ans2/=g;

			return 1;

		}

		if(!((i-L+1)&1))

		{

			while(h1<=t1&&s[q1[t1]]>=s[i-L+1])	t1--;

			q1[++t1]=i-L+1;

		}

		else

		{

			while(h2<=t2&&s[q2[t2]]>=s[i-L+1])	t2--;

			q2[++t2]=i-L+1;

		}

	}

	return 0;

}

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;

}

int main()

{

	n=rd(),L=rd(),R=rd();

	int i;

	double l=1<<30,r=0,mid;

	for(i=1;i<=n;i++)	A[i]=A[i+n]=rd(),l=min(l,(double)A[i]),r=max(r,(double)A[i]);

	for(i=1;i<=n<<1;i++)	S[i]=S[i-1]+A[i];

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

	{

		mid=(l+r)/2;

		if(check(mid))	l=mid;

		else	r=mid;

	}

	printf("%lld/%lld",ans1,ans2);

	return 0;

}