首先发现这个过程的限制比较多，那么考虑重新描述这个过程。
令 \(x_i\) 表示在第 \(i\) 个物品上使用了 \(x_i\) 张券，那么一组 \(x_{1\sim n}\) 就描述了一个方案。
方便起见，令 \(s_i\) 为前 i 个物品买完后剩了几张券，那么有：
- \(s_0 = m\)
- \(s_i = s_{i - 1} + \lfloor\frac{a_i - x_i}{c}\rfloor\)
考虑合法的 \(x_{1\sim n}\) 要满足的条件和最后的答案。
要满足的条件：
- \(x_i\le b_i\)
- \(x_i\le s_{i - 1}\)
最后的答案为 \(\sum (a_i - x_i)\)，即要求最大化 \(\sum x_i\)。
先考虑所有 \(x_i = 0\) 的情况，然后考虑变化，设 \(ds_i\) 为第 \(i\) 个物品贡献的优惠券。
基于 \(ds_i\) 的变化，可以把一个物品的 \(x_i\) 的变化拆成基于 \(3\) 种操作的变化。
- 前 \(a_i\bmod c\) 张，此时使用优惠券不影响 \(ds_i\)
- 每次操作使 \(ds_i\) 减 1 并使 \(x_i\) 加 \(c\)
- 使 \(ds_i\) 减 1 并使 \(x_i\) 加 \([0, c - 1]\)
为了方便考虑，设 \(s'_i = s_{i - 1} - x_i\)，那么条件 2 就是 \(s'_i\ge 0\)。
接下来再次考虑每种操作造成的影响。
对 \(i\) 进行操作 1/2/3 的影响分别为：
- 使 \(s'_{i\sim n}\) 全部减 \(1\)，\(x_i\) 加 \(1\)
- 使 \(s'_{i}\) 减 \(c\)，使 \(s'_{j > i}\) 减 \(c + 1\)，使 \(x_i\) 加 \(c\)
- 假设使 \(x_i\) 加 \(z\)，那么会使 \(s'_{i}\) 减 \(z\)，使 \(s'_{j > i}\) 减 \(z + 1\)
发现：
- 显然操作 2 优于操作 3，且操作 1 优于其余两个（因为相同情况下影响一定完全小于其余操作）。
- 为了进行最多次的操作 1 可以从右往左扫一遍。
- 为了进行最多次的操作 2 也可以从右往左扫一遍。
那么我们考虑动态维护 \(s'_i\) 的值。令 \(t\) 为能使用的券的个数。
对于操作 1，\(t = \min(b_i, a_i\bmod c, \min\limits_{j \ge i} s'_j)\)。
对于操作 2，\(t = \min(\lfloor\frac{b_i - x_i}{c}\rfloor, \lfloor\frac{s'_{i - 1}}{c}\rfloor, \min\limits_{j \ge i}\lfloor\frac{s'_j}{c + 1}\rfloor)\times c\)。
（我的正解的操作 3 部分的代码写得很丑陋，大概看一下就行。）
对于操作 3，考虑最优策略按能使用的券的张数从大到小，那么我们可以直接暴力模拟，\(t = \min(b_i - x_i, \min(s'_{i - 1}, d_i = \min_{j\ge i} s'_{j - 1}))\)。
发现 \(d_i\) 随 \(i\) 增大而增大。那么考虑枚举前面的限制（\(b_i - x_i\)），把 \(\ge w\) 的加入，然后看一下最大的 \(i\) 的 \(d_i\)，比较一下大小即可，可以用区间加，查询区间 min 线段树维护。
可以看一下暴力模拟的代码，正解用某些方式优化了其中的过程。
标签：lfloor,min,题解,好题,rfloor,ge,2023,操作,ds From： https://www.cnblogs.com/SkyMaths/p/18542562