事先声明

此题解为一篇洛谷题解的详细补充，这里(我才不告诉你我这道题想了好久)

有 \(n\) 个任务，记作 \(t\) 数组，由于主人公很懒，所以他每天都要睡觉，每一天都有 \(x\) 小时。

前 \(i\) 天睡觉的下限为 \(r \cdot x \cdot i\) ，其中 \(r\) 为给定实数。

求至少需要多少天才能完成任务。

考虑一种暴力做法，即模拟。

每天考虑不同的任务，能做就做，不能做则睡觉。（算贪心吗？）

question1： \(t\) 数组要排序嘛？

• 面对这个问题，我们从一般角度来看都是解不出来的，所以我们考虑转换思路。

• 我们从全局考虑这个问题

• 因为 \(\sum_{i=1}^{n} t_i\) 是恒定的，所以每一天都是独立的，也就是两天之间没有联系。

• 又因为 \(\sum_{i=1}r\cdot x \cdot i\) 也是恒定的。

• 所以总时间=睡觉的时间+工作的时间是恒定的。

• 所以 \(t\) 数组的顺序没有强制要求。

然后代码就出来了。

可以发现会被卡掉（别问为什么)，所以考虑优化。

优化？

容易发现，如果每天都可以做任务的话，时间复杂度就为 \(O(n)\) 远远够得，所以不可能会被卡

发现了什么？

有些天他整天睡觉的

而这些天都算进了我们的循环，太浪费了，我们考虑把这些天过滤掉，这样时间复杂度就为线性了！

假设当前面对的是 \(tot\) 个任务，即 \(t_{tot}\) ，目前总睡觉时间为 \(sl\) ，现在是第 \(j\) 天。

那么当 \(x-a_{tot}+sl<m \cdot j \cdot \frac{p}{q}\) ，这一天肯定做不了任务了，所以我们让他睡觉。

假设要睡 \(i\) 天觉 那么有 \(m - a_{tot} + sl + i \cdot m \ge m \cdot(i+j) \cdot \frac{p}{q}\)

简单移项可以得到 \(i \ge \cfrac{j \cdot m \cdot p - q \cdot (m - a_{tot})+sl}{m\cdot(q-p)}\)

取等号最小，所以 \(i =\left \lceil \cfrac{j \cdot m \cdot p - q \cdot (m - a_{tot})+sl}{m\cdot(q-p)} \right \rceil\) ，其中 \(\left \lceil \right \rceil\) ，为向上取整。

question2：向上取整怎么计算

• 虽然c++有向上取整的函数，但是假设我们不知道，但是我们知道， \(int\) 会自动向下取整，那么，有什么方式可以让向上取整和向下取整相互转换吗？

• 答案是有的，有个公式： \(\left \lceil \cfrac{x}{y} \right \rceil = \left \lfloor \cfrac{x+y-1}{y} \right \rfloor\)

• 怎么证明呢？

• 我们分类讨论。

1. 我们设 \(y | x\) ，则我们可以设 \(x=ky(k \in \mathbb{Z})\) ，则我们只需证 \(\left \lceil k \right \rceil = \left \lfloor k+1-1 \right \rfloor\) ，明显成立。

2. 我们设 \(x=ky+p(k,p \in \mathbb{Z})\) ， \(p \in (1,y-1]\) ， 则我们只需证 \(\left \lceil k+\cfrac{p}{y} \right \rceil = \left \lfloor k+1+\cfrac{p}{y}-\cfrac{1}{y} \right \rfloor\) ，又因为 \(p<y\) ，则原式 \(k+1=k+1\) ，显然成立。

   于是，这道题就做完了，这里配上代码

   #include

   using namespace std;

   #define int long long

   const int MAXN = 1e5 + 7;

   int n, x, p, q, t[MAXN];

   signed main() {
   ios::sync_with_stdio(false);
   cin.tie(NULL);//cin的加速

   cin >> n >> x >> p >> q;
   for (int i = 1; i <= n; i ++) cin >> t[i];
   
   int tot = 1, sl = 0;
   for (int j = 1; ; j ++) {
       if ((x - t[tot] + sl) * q < x * p * j) {//需要睡觉
           int i = (x * p * j - (x - t[tot] + sl) * q + (x * (q - p)) - 1) / (x * (q - p));//我们推出来的式子
           j += i, sl += i * x;//加上去
       }
       int ans = x;//ans：睡觉时间，一开始全天都要睡觉
       while (true) {
           if (tot > n) break;//做完了
           if (ans <= t[tot]) break;//不够做
           if ((ans - t[tot] + sl) * q < x * p * j) break;//不够做
           ans -= t[tot], tot++;//睡觉时间减掉，tot++
       }
       sl += ans;//睡觉时间加上ans
       if (tot > n) {
           cout << j << endl;//输出
           break;
       }
   }
   return chen_zhe;

   }

完结撒花✿✿ヽ(°▽°)ノ✿