CF1671C Dolce Vita 题解

jiangtaizhe001 · 2022-04-26 20:23:23 · 题解

可能更好的阅读体验

题目大意

摘自洛谷的翻译：
动乱的时代就要来了，因此你决定储备一些糖。有 n 个商店卖糖：第 i 个商店一包糖要 a_i 硬币，但每人每天只能买一包。所以你为了买多几包糖，你得去好几家商店。
另外一个问题就是糖价每天都在上涨：第一天 a_i 硬币一包，第二天 a_i+1 硬币一包，第三天 a_i+2 硬币一包。对于每家商店都是如此。
然而，你每天的预算只有 x 硬币。也就是说，你每天花在糖上的钱不能超过 x 硬币。如果你一天的预算没有花完，第二天也不能花前一天剩下来的钱。
最终，每包糖的价格都会超过 x，你将一包糖都买不起。所以，在那之前，你最多能买多少包糖？

题目解析

不难想到每天肯定买便宜的糖，由于每天所有糖涨价的速度是一样的，所以相对的大小不会变。
所以首先我们需要排序。
然后直接暴力做显然是不可行的。
我们可以先做一次前缀和，枚举 i 从 1 到 n，然后直接二分出最小的 s 使得第 s 天不买不起 i 包糖。
复杂度 \Theta\left(n\log x\right)。

参考代码：

void work(){
    n=read(); x=read(); int i; for(i=1;i<=n;i++) a[i]=read(); sort(a+1,a+n+1); ans=0;
    for(i=1;i<=n;i++) a[i]+=a[i-1];
    for(i=1;i<=n;i++){
        l=-1,r=x+10;
        while(l+1<r){
            mid=(l+r)>>1;
            if(a[i]+(ll)mid*(ll)i<=x) l=mid; else r=mid;
        } ans+=l+1;
    } print(ans),pc('\n');
}