bzoj 3874: [Ahoi2014&Jsoi2014]宅男计划

#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>#define ll long long#define mem(a,b) memset(a,b,sizeof(a))using namespace std;const int N=1006;struct son{ ???ll t,w;}ji[N],q[N];int con;bool ok_t(son a,son b){ ???if(a.t==b.t) ???????return a.w<b.w; ???return a.t<b.t;}bool ok_w(son a,son b){ ???if(a.w==b.w) ???????//return a.t>b.t; //wrong reason:不能a.t>b.t，因为有可能用到 ???????return a.t<b.t; ???return a.w<b.w;}int n;ll M,F;ll check(ll x){ ???ll ans=0,temp,le=M-F*x,fina,can; ???if(le<0) ???????return 0; ???for(int i=1;i<=con;++i) ???{ ???????if(le<0) ???????????break; ???????temp=le/q[i].w; ???????/*fina=min(temp,q[i].t*x-ans ); ???????if(fina<0) ?//炸long long了 ???????????while(1);*/ ???????can=(temp+ans-1)/x+1; ???????if(can>q[i].t) ??// T_M_D 炸long long ???????????fina=q[i].t*x-ans; ???????else ???????????fina=temp; ???????ans+=fina; ???????le-=fina*q[i].w; ???} ???return ans;}ll work(){ ???ll ans=0; ???ll l=1,r=M/(F+q[1].w),mid,midmid,vmid,vmidmid; ???while(l+15<=r) ???{ ???????mid=l+((r-l)/3); ???????midmid=r-((r-l)/3); ???????vmid=check(mid); ???????vmidmid=check(midmid); ???????if(vmid>vmidmid) ???????{ ???????????r=midmid; ???????????if(ans<vmid) ???????????????ans=vmid; ???????} ???????else ???????{ ???????????l=mid; ???????????if(ans<vmidmid) ???????????????ans=vmidmid; ???????} ???} ???for(ll i=l;i<=r;++i) ???{ ???????vmid=check(i); ???????if(ans<vmid) ???????????ans=vmid; ???} ???return ans;}int main(){ ???//freopen("in.in","r",stdin); ???scanf("%lld%lld%d",&M,&F,&n); ???for(int i=1;i<=n;++i) ???{ ???????scanf("%lld%lld",&ji[i].w,&ji[i].t); ???????++ji[i].t; ???} ???sort(ji+1,ji+1+n,ok_w); ???con=0; ???q[++con]=ji[1]; ???for(int i=2;i<=n;++i) ???????if(ji[i].t>q[con].t) ???????????q[++con]=ji[i]; ???//sort(q+1,q+1+con,ok_t); // 已经是按时间排序了.... ???cout<<work();}