5
16
2016
0

[BZOJ3874] [Ahoi2014]宅男计划

三分送外卖次数,然后贪心的买外卖就好了

过程:首先我们要每次买最便宜的外卖一份,这样保证我们可以过送外卖次数的天数

然后还有剩下的钱我们就优先选择便宜的来填满这些食物的保质期,填满了之后我们再选择次便宜的填满保质期,以此类推

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;

const int N=205;

int n,Top;
long long m,f;

struct Food{
long long p,s;
friend bool operator<(Food A,Food B){return A.p<B.p;}
}food[N],Q[N];

long long Get(long long x){
long long mo=m-x*f,day=0,ans=0,last;
if(mo<0)return 0;
for(int i=1;i<=Top;i++){
	if(day<=Q[i].s){
		last=min(Q[i].s-day+1,mo/Q[i].p/x);
		ans+=last*x;
		mo-=last*Q[i].p*x;
		day+=last;
	}
	if(day<=Q[i].s){
		last=min(x,mo/Q[i].p);
		ans+=last;
		mo-=Q[i].p*last;
		day++;
	}
}
return ans;
}

long long Solve(){
long long l=1,r=m/(f+Q[1].p),ans1=0,ans2=0,ans=max(Get(l),Get(r));
while(l<=r){
    long long mid1=l+(r-l)/3,mid2=r-(r-l)/3;
    ans1=Get(mid1);ans2=Get(mid2);
    ans=max(ans,max(ans1,ans2));
    if(ans1<ans2)l=mid1+1;
    else r=mid2-1;
}
return ans;
}

int main(){
freopen("3874.in","r",stdin);
freopen("3874.out","w",stdout);
scanf("%lld %lld %d",&m,&f,&n);
for(int i=1;i<=n;i++)scanf("%lld %lld",&food[i].p,&food[i].s);
sort(food+1,food+n+1);
Q[++Top]=food[1];
for(int i=2;i<=n;i++){
	if(food[i].s>Q[Top].s)Q[++Top]=food[i];
}
printf("%lld\n",Solve());
return 0;
}
Category: BZOJ | Tags: OI bzoj | Read Count: 642

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com