Unleafy · blog

2026 Summer Day27

216 words1 min readPageviews --#模拟赛
Categories记录Series2026 Summer 26/27

2026 Summer Day27

T1 company

发现如果 x<yx < y，那么操作 1 完全是没用的。所以只需要考虑 x≥yx \ge y 的情况。

将每个饼干的需求拆成 ci=qx+rc_i = qx + r 的形式，显然用 qq 次操作 1 是不劣的。只需要考虑余数 rr 的情况。

  • y<r<xy < r < x，那么可以贪心地再取一次 xx，显然比取多于 1 次 yy 要优秀。
  • 否则将这些剩余的 rr 扔给操作 2 继续处理。

所以 cc 的贡献就是

w⁡(c)={cx≤y⌊cx⌋y+min⁡(c mod x,y)x>y\operatorname{w}(c) = \begin{cases} c & x \le y \\ \lfloor \frac{c}{x} \rfloor y + \min(c \bmod x, y) & x > y \end{cases}

所以最后最晚完成的日期就是

max⁡d(d+⌈∑si≥dw⁡(ci)y⌉−1)=⌈max⁡d(y(d−1)+∑si≥dw⁡(ci))y⌉\max_d(d + \lceil \frac{\sum_{s_i \ge d} \operatorname{w}(c_i)}{y} \rceil - 1) = \lceil \frac{\max_d(y(d-1) + \sum_{s_i \ge d} \operatorname{w}(c_i))}{y} \rceil

所以用线段树维护区间和和区间 max⁡\max 即可。

Comments

Quiet notes for this article.