题解 P4040 【[AHOI2014/JSOI2014]宅男计划】

· · 题解

（作为一道省选题，这题还是比较简单的，连我这种大蒟蒻都能水过去，不过竟然没有人来发题解，那么我就来写一份题解好了）

三分这题主要是运用三分和贪心的思想来做（反正我是这样做的，不过网上还有别的dalao用的是模拟退火，有志向的同学可以去看一看，反正我没有看懂）。

这题的关键是看出购买外卖的次数与能够宅的天数的关系是一个近似于单峰的函数，既然是单峰的函数，那么找出最大值就自然会使用三分购买外卖的次数了。（看出单峰函数的方法我也不知道，主要是一个一个去试，然后就能发现是单峰的了）

三分模板（类型为double）：

    while(r-l<eps){
        double block=(r-l)/3;
        midl=l+block;midr=r-block;
        if(f(midl)>f(midr)){
            l=midl
        }else{
            r=midr;
        }
    }

然后就是对于每种次数求出最大能够达到的天数，因为数据大小有10^18，所以放弃使用背包，运用贪心的思想求解。具体的贪心是将所有的钱减去送外卖的总费用后平均分成多份，然后对每一份钱进行贪心，最后把剩下的所有钱进行贪心，前面的天数乘以份数再加上后面的天数就是当前次数的最大存活天数。 AC代码：

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    long long m,f,n,l,r,midr,midl,maxn;
    struct food {
        long long p,s;
    } a[205];
    bool cmp(food a,food b) {//定义快排
        if(a.p!=b.p) return a.p<b.p;
        else return a.s>b.s;
    }
    long long get(long long t) {//贪心
        long long v,ans,now,w,k,p,j;
        v=m-t*f;//减去叫买卖所花费的钱
        w=v/t;//用w存每一份的钱
        k=v-w*t;//用k存一开始剩下来的钱
        ans=0;now=0;//初始化
        if(v<0)return 0;//当一开始就把钱花完了，自然就要退出
        for(long long i=1; i<=n; i++) {//贪心主体
            if((a[i].s>=now)&&(w-a[i].p>=0)) {//最便宜的能吃几天就吃几天，吃不了了再去找下一个能吃的吃
                p=min(a[i].s+1-now,w/a[i].p);
                now+=p;
                w-=p*a[i].p;
            }
            j=i;//用j储存选择的食品数量
            if(w-a[i].p<0)break;//因为按价格排序，当前的买不起了，剩下的都买不起了
        }
        k+=w*t;//将剩下的钱全存到k里
        for(long long i=j; i<=n; i++) {//对k进行贪心，从j开始，能吃的就买
            if((a[i].s>=now)&&(k-a[i].p>=0)) {
                p=min(k/a[i].p,t);
                ans+=p;
                k-=p*a[i].p;
            }
            if(ans>0)break;//因为剩下的钱不可能做到每次外卖都多买一天的量
        }
        //所以一旦ans有值，说明已经用过了，所以剩下的一定买不了了
        return t*now+ans;
    }
    int main() {
        cin>>m>>f>>n;
        for(int i=1; i<=n; i++) {
            cin>>a[i].p>>a[i].s;
        }
        sort(a+1,a+n+1,cmp);//优先吃便宜的，所以对食品价格进行排序，价格相同时保质期长的在前
        l=1;
        if(f!=0) {//特判f为0的情况
            r=(m/f)+1;//次数最大为总钱数除以每次送外卖的次数
        } else r=m+1;
        while(l<r) {//三分
            midl=l+(r-l)/3;
            midr=r-(r-l)/3;
            if(get(midl)>=get(midr)) {
                r=midr-1;//因为是整形，所以赋值时要-1，下面l也要+1
            } else {
                l=midl+1;
            }
    //        cout<<l<<" "<<r<<" "<<get(midl)<<" "<<get(midr)<<endl;
        }
        cout<<get(l);//好像输出l或r都可以
        return 0;
}