题目传送门
【题目大意】
有$n$种食物，第$i$种食物的价格为$p_i$，保质期为$s_i$。当前有$m$元钱，每次外卖要额外花费$f$元，求在保证不吃到过期食物且每天吃一份食物的情况下，最多可以吃多少天？
【思路分析】
emmmm其实想到了差不多的贪心思路，就是每次买外卖的时候尽量先买钱少的，然后如果某种食物价格贵还保质期短，那显然不买。
现在问题就是怎么确定买外卖的次数？
答案是三分(因为二分会挂)，这是一个单峰函数(别问我怎么知道的我也不会证)，所以可以用三分完美解决QwQ
然后就……over啦？看代码注解叭QwQ
【代码实现】
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 #define g() getchar() 8 #define rg register 9 #define ll long long 10 #define go(i,a,b) for(rg ll i=a;i<=b;i++) 11 #define back(i,a,b) for(rg ll i=a;i>=b;i--) 12 #define db double 13 #define il inline 14 #define pf printf 15 #define mem(a,b) memset(a,b,sizeof(a)) 16 using namespace std; 17 ll fr(){ 18 ll w=0,q=1; 19 char ch=g(); 20 while(ch<'0'||ch>'9'){ 21 if(ch=='-') q=-1; 22 ch=g(); 23 } 24 while(ch>='0'&&ch<='9') w=(w<<1)+(w<<3)+ch-'0',ch=g(); 25 return w*q; 26 } 27 const int N=202; 28 ll n,m,F,ans; 29 struct food{ 30 ll p,s; 31 }f[N]; 32 il ll cal(ll x){//x表示订外卖的次数 33 ll lft=m-1ll*x*F,date=0,as=0; 34 //lft记录剩下的钱数,date记录上一种外卖吃完后的日期,as记录活的天数 35 if(lft<=0) return 0; 36 go(i,1,n){ 37 ll t=f[i].s-date; 38 if(t<=0) continue;//如果这个外卖保质期不够就不吃 39 if(1ll*f[i].p*t<=lft/x) as+=x*t,lft-=1ll*f[i].p*x*t,date=f[i].s; 40 else return as+lft/f[i].p; 41 } 42 return as; 43 } 44 il bool cmp(food x,food y){return x.p<y.p;} 45 int main(){ 46 //freopen("","r",stdin); 47 //freopen("","w",stdout); 48 m=fr();F=fr();n=fr(); 49 go(i,1,n) f[i]=(food){fr(),fr()+1}; 50 //保质期+1相当于是订外卖在第0天,开始吃外卖在第1天 51 sort(f+1,f+1+n,cmp); 52 ll l=1,r=m/F; 53 while(r-l>=5){ 54 ll ml=((l<<1)+r)/3,mr=(l+(r<<1))/3;//三分 55 ll asl=cal(ml),asr=cal(mr); 56 if(asl<=asr) l=ml; 57 if(asl>=asr) r=mr; 58 } 59 go(i,l,r) ans=max(ans,cal(i)); 60 pf("%lld\n",ans); 61 return 0; 62 } 代码戳这里转载于:https://www.cnblogs.com/THWZF/p/11557559.html
