Educational Codeforces Round 135 (Rated for Div. 2) E. Red-Black Pepper（贪心+数论）

 

 

题解

缝合题

第一段是贪心求出所有红黑胡椒粉分配个数的最大价值

第二段是数论求出可行解中的最优解

第一段：

假设我们全选bi，那么枚举下一种胡椒粉分配时，会把一个bi换成ai

所以直接按照ai-bi大小排序

这样可以保证每次选择的bi换位ai是最优的

第二段：

一个a胡椒粉套装含x包，一个b胡椒粉套装含y包

exgcd求出来x*p+y*q=n的一个特解

接下来我们应该枚举所有的可行解

p=p0+k*y/gcd

q=q0-k*x/gcd

可惜直接枚举会超时

我们发现第一段的答案是一个上凸函数

我们可以三分

可惜太麻烦了

我们发现第一段答案的最高点的位置就是ai-bi由正转负的位置

所以可以通过数学运算直接解出极值点附近的k

然后为了保证正确性，我们枚举一下这个k附近的所有解就好了

代码：

#include
#include
#include
#include
using namespace std;
#define N 300005
struct node{
	int a,b;
	bool operator < (const node &t)const{
		return a-b>t.a-t.b;
	}
}dish[N];
#define LL long long
LL ans[N];
void exgcd(LL a,LL b,LL &gcd,LL &x,LL &y)
{
    if(!b){x=1;y=0;gcd=a;}
    else{
        exgcd(b,a%b,gcd,y,x);
        y-=x*(a/b);
    }
}
int main()
{
	int n,i;LL sum=0;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d%d",&dish[i].a,&dish[i].b);
		sum+=1ll*dish[i].b;
	}
	sort(dish+1,dish+n+1);
	ans[0]=sum;
	int chp=0;
	for(i=1;i<=n;i++){
		sum=sum-dish[i].b+dish[i].a;
		if(dish[i].a-dish[i].b>=0)
			chp=i;
		ans[i]=sum;
	}
	//printf("chp:%d\n",chp);
	int m;
	LL gcd,x,y,p,q;
	scanf("%d",&m);
	for(i=1;i<=m;i++){
		scanf("%lld%lld",&x,&y);
		exgcd(x,y,gcd,p,q);//xp+yq=gcd(x,y)
		if(n%gcd!=0)
			printf("-1\n");
		else{
			LL tmp=1ll*n/gcd;
			p*=tmp;q*=tmp;
			//xp+yq=n
			//x*p'=x*(p+k*y/gcd) = chp
			//q'=q-k*x/gcd
			//printf("pq::%lld %lld\n",p,q);
			LL k=floor(1.0*(1.0*chp/x-p)/y*gcd);
			LL realans=-1;
			for(LL K=k-3;K<=k+3;K++)
				if(x*(p+K*y/gcd)>=0&&x*(p+K*y/gcd)<=n&&y*(q-K*x/gcd)>=0&&y*(q-K*x/gcd)<=n)
					realans=max(realans,ans[x*(p+K*y/gcd)]);
			printf("%lld\n",realans);
		}
	}
}