Bzoj 3874: [Ahoi2014&Jsoi2014]宅男计划 三分+贪心

3874: [Ahoi2014&Jsoi2014]宅男计划

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 861  Solved: 336
[Submit][Status][Discuss]

Description

 【故事背景】

自从迷上了拼图，JYY就变成了个彻底的宅男。为了解决温饱问题，JYY

不得不依靠叫外卖来维持生计。

【问题描述】

外卖店一共有N种食物，分别有1到N编号。第i种食物有固定的价钱Pi和保质期Si。第i种食物会在Si天后过期。JYY是不会吃过期食物的。

比如JYY如果今天点了一份保质期为1天的食物，那么JYY必须在今天或

者明天把这个食物吃掉，否则这个食物就再也不能吃了。保质期可以为0天，这

样这份食物就必须在购买当天吃掉。

JYY现在有M块钱，每一次叫外卖需要额外付给送外卖小哥外送费F元。

送外卖的小哥身强力壮，可以瞬间给JYY带来任意多份食物。JYY想知道，在

满足每天都能吃到至少一顿没过期的外卖的情况下，他可以最多宅多少天呢？

Input

第一行包含三个整数M，F和N。

接下来N行，第i行包含两个整数Pi和Si。

Output

输出仅包含一行一个整数表示JYY可以宅的最多的天数。

Sample Input

32 5 2
5 0
10 2

Sample Output

3

HINT

【样例说明】

JYY的最佳策略是：

第一天买一份食物1和一份食物2并且吃一份食物1；

第二天吃一份食物2；

第三天买一份食物1并且吃掉。

【数据规模与约定】

对于100%的数据满足0<=Si<=10^18,1<=F,Pi,M<=10^18,1<=N<=200

　　当时还以为是一个动归题，想半天想不出来，直接跪了。一看题解 三分？？！！

　　好吧，我之前貌似就打过一次三分，还打挂了，从此以后再也没去打过，讲解也只是听stdafx学长讲过，都忘的差不多了，所以赶紧打一道压压惊。

　　众所周知三分主要运用在单峰函数上，但这道题为什么是单峰函数呢？据出题人说他只是想让大家去猜，至于证明，网上我只找到一份，还无法访问……那我就口胡了。

　　假设不考虑保质期，那么外卖小哥一定是来的越少越好。同理，如果外卖小哥不要钱，那么我们买的越便宜越好，所以，这两者相互牵绊，我们如果叫太多次外卖我们就不得不去用更少的钱去买吃的，而如果我们买太少次外卖，保质期长的往往要贵一些，我们可能会买太多太贵的东西。所以应该有那么一个中间值是最好的。中庸之道？

　　首先，我们一定要去贪心去掉那些又贵还容易过期的。然后重新构造出所有食品，然后套三分check。

　　假设我们已经知道当前要check的买外卖的次数，那么我们可以将所有食品按照价格从小到大重新排序，然后依次枚举，我们可以想到，为了多宅一会，我们每次买外卖的钱一定是尽可能接近甚至相等的，那我们就可以对于一个物品分两种讨论。第一，我们每一次买外卖我们都让小哥带一份来，这个在容易不过，只要注意保质期的限制就好了。第二，也是较难的，散着买，我们买了东西后很有可能会有剩余的钱，够买一些吃的却买不了一个周期，这时，我们就要去判断我们是否能够去把它加到一些区间里去，让这些钱物尽其用。首先，判断条件依然是保质期，不过由于我们已经无法再买一个周期，我们能买的份数就是现有钱数/价格。而这些散着买的物品对于周期的贡献也是要记为1的。有的人可能会像我一样，疑惑这会不会对之后我们散着买的食品造成影响。

　　当然不会，我们假设后面有一种食品可以被填补在当前并未分配到我们散着买食品的区间中，但由于我们T++，无法被放入，那么我们想一想，之前我们散着购买食品的时候为什么没有给这个区间也买上食品呢？因为钱已经不够花了，而我们又是将物品按照价格排的序，因此这种情况根本不会存在。

 #include <iostream>
 #include <cstdlib>
 #include <cstdio>
 #include <cstring>
 #include <queue>
 #include <algorithm>
 #include <cmath>
 #include <map>
 #include <set>
 #define N 205
 using namespace std;
 long long n,m,f,zz,ans;
 struct no
 {
     long long p,s;
 }node2[N],node[N];
 bool px(no a,no b)
 {
     if(a.s==b.s)return a.p<b.p;
     return a.s>b.s;
 }
 bool px2(no a,no b)
 {
     return a.p<b.p;
 }
 long long check(long long x)
 {
     long long money=m-f*x,T=,sum=,js;
     if(money<)return ;
     for(int i=;i<=n;i++)
     {
         if(T<node[i].s)
         {
             js=min(node[i].s-T,money/(x*node[i].p));
             sum+=x*js;
             T+=js;
             money-=node[i].p*js*x;
         }
         if(T<node[i].s)
         {
             js=money/node[i].p;
             sum+=js;
             T++;
             money-=node[i].p*js;
         }
     }
     return sum;
 }
 int main()
 {
     scanf("%lld%lld%lld",&m,&f,&n);
     for(int i=;i<=n;i++)
     {
         scanf("%lld%lld",&node2[i].p,&node2[i].s);
         node2[i].s++;
     }
     sort(node2+,node2++n,px);
     node[]=node2[];zz=;

     for(int i=;i<=n;i++)
     {
         if(node2[i].p>=node2[i-].p)continue;
         zz++;
         node[zz]=node2[i];
     }
     n=zz;
     sort(node+,node++n,px2);
     long long li=,ri=m/(f+node[].p),lm,rm;
     while(li<=ri)
     {
         lm=li+(ri-li+)/,rm=ri-(ri-li+)/;
         long long ans1=check(lm),ans2=check(rm);
         if(ans1>=ans2)
         {
             ans=max(ans,ans1);
             ri=rm-;
         }
         else
         {
             ans=max(ans,ans2);
             li=lm+;
         }
     }
     printf("%lld\n",ans);
     return ;
 }