三分送外卖次数，然后贪心的买外卖就好了
过程：首先我们要每次买最便宜的外卖一份，这样保证我们可以过送外卖次数的天数
然后还有剩下的钱我们就优先选择便宜的来填满这些食物的保质期，填满了之后我们再选择次便宜的填满保质期，以此类推
#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;
}
评论 (0)
