题目链接:
while(1)gugu(while(1))
闲扯
考场上怕T2正解写挂其他两题没管只打了暴力,晚上发现这题思维挺妙的
同时想吐槽出题人似乎热衷卡常...我的巨大常数现在显露无疑QAQ
分析
这道题yy出了一个似乎比solution更好理解的解法,一开始有\(n\)条一次函数,就有\(2^n\)种函数集合,显然每个集合也是一个一次函数\(T_i(x)=k_i x+b_i\)
我们把这个集合分成两种\(k_i<=0\)和\(k_i>0\),显然如果答案最后最大值的函数集合是第一种,那么显然肯定是在\(x=0\)取到的
所以我们单独把\(x=0\)拎出来考虑就可以不考虑第一种函数集合的贡献了
对于第二种\(k_i>0\)的函数集合,应该很容易发现\(max(T_i(x))\)是单调递增的的图像,可以二分找到答案要求的点
然后这题就做完了
对于0的处理其实就是把\(b_i\)最大且大于0的拿出来看看是否大于等于S就好了,虽然最后这样的函数集合不一定是第一种\(k_i<=0\)但是一定考虑进去了
二分的时候也是贪心把该点的处于前\(m\)大且大于0的单个一次函数值加起来判断一下就好了
这里有个骚操作nth_ment(l,pos,r,cmp),表示将容器中\([l,r)\)种第pos个位置的元素变成第\(pos\)大/小(视cmp函数决定)，同时pos前都是大/小于第pos大/小的元素,pos后类似
代码
#include#include #include #include #include #include #include #include #define ll long long #define ri register int using std::min;using std::max;using std::nth_element;inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}template inline void read(T &x){ x=0;int ne=0;char c; while(!isdigit(c=nc()))ne=c=='-'; x=c-48; while(isdigit(c=nc()))x=(x<<3)+(x<<1)+c-48; x=ne?-x:x;return ;}const int maxn=1000005;const int inf=0x7fffffff;ll v[maxn],ki[maxn],bi[maxn];int n,m;ll s;bool ok(int x){ for(ri i=1;i<=n;i++)v[i]=ki[i]*x+bi[i]; nth_element(v+1,v+m,v+n+1,std::greater ()); ll sum=0; if(sum>=s)return 1; for(ri i=1;i<=m;i++){ if(v[i]>0)sum+=v[i]; if(sum>=s)return 1; } return 0;}int main(){ freopen("merchant.in","r",stdin); freopen("merchant.out","w",stdout); read(n),read(m),read(s); for(ri i=1;i<=n;i++){ read(ki[i]),read(bi[i]); } if(ok(0)){puts("0");exit(0);} int L=1,R=1e9,ans; while(L<=R){ int mid=(L+R)>>1; if(ok(mid))ans=mid-1,R=mid-1; else L=mid+1; } printf("%d\n",ans+1); return 0;}