题意：

n种食物，每种有价钱和保质期。每次叫外卖要F元，可以购买任意多份食物。共有m元，问一共能过多少天使得每天都能吃到一份不过期的食物。n≤200，其他都≤10¹⁸

题解：

先排序+单调队列去掉那些价钱贵保质期反而短的外卖，剩下的队列按保质期从短到长排（也就是价钱从便宜到贵排）。然后有结论：生存天数为以叫外卖次数为自变量的单峰函数。因此三分叫外卖次数（注意上界为m/最便宜外卖的价钱），如何根据叫外卖次数求生存天数呢？又有结论：每次叫外卖间隔时间越平均越优。设叫外卖次数为k，从便宜到贵买，依次扩充叫外卖间隔时间，当最后钱不够买齐k组当前食物时，则能买多少组买多少。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 #define ll long long 6 #define maxn 300 7 using namespace std; 8  9 inline ll read(){10     char ch=getchar(); ll f=1,x=0;11     while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1; ch=getchar();}12     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();13     return f*x;14 }15 struct nd{ll p,s;}; nd a1[maxn],a2[maxn];16 ll p[maxn],s[maxn],m,f,l,r,ans; int n;17 bool cmp(nd a,nd b){
   return a.s==b.s?a.p>b.p:a.s
        
         =day){22             ll a=min(cost/a2[i].p/k,a2[i].s-day+1); day+=a; ans+=a*k; cost-=a*k*a2[i].p;23         }24         if(a2[i].s>=day){25             ll a=min(k,cost/a2[i].p); day++; ans+=a; cost-=a*a2[i].p;26         } 27     }28     return ans;29 }30 int main(){31     m=read(); f=read(); n=(int)read(); inc(i,1,n)a1[i].p=read(),a1[i].s=read(); sort(a1+1,a1+1+n,cmp);32     r=1; a2[r]=a1[1];33     inc(i,2,n){
   while(r&&a2[r].p>a1[i].p)r--; a2[++r]=a1[i];} n=r;34     l=1; r=(m/(f+a2[1].p)); ans=0;35     while(l<=r){36         ll mid1=l+(r-l)/3,mid2=r-(r-l)/3,c1=calc(mid1),c2=calc(mid2);37         if(c1
         
          c2)ans=max(ans,c1),r=mid2-1;39         else ans=max(ans,c1),l=mid1+1,r=mid2-1;40     }41     printf("%lld",ans); return 0;42 }
         
        
       
      
     

 

20160719