【BZOJ3874】[AHOI&JSOI2014]宅男计划(贪心,三分)

【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;
}
上一篇:SE Springer小组《Spring音乐播放器》软件需求说明3


下一篇:CMMI摘要