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

来一发三分套二分的题解 首先，我们发现这道题是个应用题，数据范围极大，省选难度 所以是考你三分法了，然后我们对于这道题，需要找几个贪心的结论 1.对于某些保质期短又贵的垃圾食品，我们坚决不要，所以可以他们删掉，所以食品的价格随保质期单增 2.如果当前买的轮次c固定，那么当前最优解仅有买M和M+1两种天数，也就是说，天数接近的时候最优，证明如果有一个方案天数是不接近的，那么把大的往小的上补，因为保质期随价格单增，肯定会变优 那么我们发现一件事，如果给定钱数，那么我们能存活到第几天是可以二分的，又因为刚才的结论2，我们可以把钱均分为c份，二分出一个存活时间k，我们发现，剩下的钱一定不能所有的天都买k+1天的量但是有几天可以所以，我们列出了总存活天数T与买的轮次C的函数 T=(M-cost(k)\*c-c\*f)/(cost(k+1)-cost(k))+k\*c ,k=D((M-C\*f)/C) 打表找规律发现这个函数单峰，可以三分求最值（不会证明，ε=ε=ε=┏(゜ロ゜;)┛逃） _（其实有一个二分套三分是可以证明单峰的，然而我们发现会爆long long）_ 上代码~ ```C #include<cstdio> #include<algorithm> using namespace std; typedef long long ll; int n;int cnt;ll m;ll f; struct food { ll cst;ll kep; friend bool operator <(food a,food b){return a.kep<b.kep;} }tp[210],fo[210]; inline ll cost(ll t)//计算存活到t的花费 { ll res=0; for(int i=1;i<=cnt;i++) { if(res<0){return -1;} if(t>fo[i].kep){res+=fo[i].cst*fo[i].kep;t-=fo[i].kep;} else {res+=fo[i].cst*t;return res;} }return -1;//这里是避免爆INF } inline ll calcd(ll pm)//计算花多少钱可以存活多少天 { ll l=0;ll r=pm; while(l<r)//单调可以二分 { ll mid=(l+r+1)/2;ll y=cost(mid); if(y==-1||y>pm){r=mid-1;}else {l=mid;} } return r; } inline ll calct(ll r)//计算T { ll rest=m-r*f;if(rest<0||rest>m){return 0;}//还是避免爆longlong ll pm=rest/r;ll k=calcd(pm);if(k==0){return 0;} ll c2=cost(k+1);ll c1=cost(k);if(c2==-1){return r*k;} else {rest-=c1*r;return rest/(c2-c1)+r*k;} } int main() { scanf("%lld%lld%d",&m,&f,&n); for(int i=1;i<=n;i++){scanf("%lld%lld",&tp[i].cst,&tp[i].kep);} sort(tp+1,tp+n+1);tp[0].kep=-1;fo[0].kep=-1; for(int i=1;i<=n;i++)//单调栈去掉无用的东西 {while(cnt!=0&&tp[i].cst<fo[cnt].cst){cnt--;}fo[++cnt]=tp[i];} for(int i=cnt;i>=1;i--){fo[i].kep-=fo[i-1].kep;}//后向差分方便计算 ll l=1;ll r=m/f+1;//三分法求函数最值 while(r-l>5)//缩小区间 { ll x1=l+(r-l)/3;ll x2=l+((r-l)*2)/3; ll y1=calct(x1);ll y2=calct(x2); if(y1<y2){l=x1;}else {r=x2;} } ll res=calct(l);//然后暴力枚举最大值 for(ll i=l+1;i<=r;i++){res=max(res,calct(i));} printf("%lld",res);return 0;//拜拜程序~ } ```