AtCoder ABC309 C - Medicine

2huk · 2023-07-08 22:23:21 · 题解

题目描述

医生给 Snuke 开了 N 种药，第 i 种药品需要在 1 \sim a_i 天中每天服用 b_i 包。问 Snuke 第一次喝的药包数 \le K 是第几天。

## 分析如果 $a_i$ 比较小，那么我们可以维护一个数组表示第 $i$ 天服的药一共有多少包。这样的话差分即可。但是本题中 $a_i$ 过大，首先时间超限，其次数组开不下，那么就考虑其他做法。观察数据范围，$a_i$ 值域很大，但总数 $N$ 很小（起码不会超时间和空间），那么就考虑类似离散化的做法。具体地，定义一个 `pair` 类型的数组 `a`，其中 `a[i].first` 表示第 $i$ 种药的服用天数，`a[i].second` 表示第 $i$ 种药每天需要服的包数（接下来我们定义 $d_i$ 表示 `a[i].first`，$t_i$ 表示 `a[i].second`）。那么首先按照 $d_i$ 值从小到大排序，然后依次求出每一段**相同的区间内**每天的服用药包数。 > 这里”相同的区间“指这一段区间内所需要服用的药包数都是相同的。怎么求呢？首先我们统计出所有的药的总包数 $S$，然后从前往后考虑每一种药。很显然的是，越往前的某天比越往后的某天的服用的药品多。对于第 $1$ 天，需要服用所有的药，也就是 $S$ 包药；第 $2$ 天可能会少一些（如果 $d_1 = 1$，那么则需要服用 $S - t_1$ 包药）；第 $3$ 天可能还会少一些……照这样计算，对于每个时间段的分割点（也就是 $d_i$），下一个时间段内的每天服用量为 $S - t_i$，然后别忘了更新 $S$ 的值。假如我们把算出的每天服用量存入 $p_i$ 中，也就是在第 $i$ 个时间段内每天需要服用 $p_i$ 包药，那么寻找答案只需要找最后一个 $p_i > K$ 的 $d_i + 1$ 即可。求出这个值可以二分（$\Theta(\log n)$），当然直接暴力（$\Theta(n)$）也可以。 [代码在此](https://www.luogu.com.cn/paste/tognt82u)。