【BZOJ3874】[AHOI&JSOI2014]宅男计划（贪心，三分）

题面

BZOJ

洛谷

题解

大力猜想一最长的天数和购买外卖的总次数是单峰的。感性理解一下就是买\(0\)次是\(0\)，买\(inf\)次也是\(0\)，在中间某次可能取到最优值。然而这样子可能是多峰的，所以也可以退火处理。

现在假装我们知道了购买外卖的总次数\(k\)，那么我们的问题就变成了如何确定每种外卖购买方案。

首先将所有外卖按照价格排序，显然只要没有过期那么一定会购买尽可能多的更便宜的外卖。

假设对于最便宜的外卖，其过期的天数是\(s\)，那么我们一定会在每次购买的时候都买\(s\)份，那么接下来的每一份外卖都是类似的处理。

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

#define ll long long

inline ll read()

{

	ll x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

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

	return t?-x:x;

}

ll m,F,n;

struct Food{ll p,s;}p[250];

bool operator<(Food a,Food b){return a.p<b.p;}

ll Calc(ll c)

{

	ll M=m-F*c,ans=0,t=0;if(M<=0)return 0;

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

		if(p[i].s>t)

		{

			ll d=p[i].s-t;

			if(1.0*p[i].p*c*d<=M)ans+=c*d,M-=p[i].p*c*d;

			else{ans+=M/p[i].p;break;}

			t=p[i].s;

		}

	return ans;

}

int main()

{

	m=read();F=read();n=read();

	for(int i=1;i<=n;++i)p[i].p=read(),p[i].s=read()+1;

	sort(&p[1],&p[n+1]);

	ll l=0,r=m/F,ret=0;

	while(r-l>=5)

	{

		ll p0=l+(r-l+1)/3,p1=r-(r-l+1)/3;

		ll d0=Calc(p0),d1=Calc(p1);

		if(d0<=d1)l=p0;else r=p1;

	}

	for(ll i=l;i<=r;++i)ret=max(ret,Calc(i));

	printf("%lld\n",ret);

	return 0;

}