洛谷-P14333 [JOI2021 预选赛 R2] 安全检查 / Safety Inspection
tag: 二分答案，贪心
一条数轴，上面有 $ N $ 个设施，设施 \(i\) 的位置坐标为 \(A_i\)。对这些设施进行安全检查。
设施 \(i\) 有 $ B_i $ 个必须检查的项目，有 \(K\) 名工人可执行检查工作。
开始时，所有工人均位于坐标 \(0\) 处。检查开始后，每位工人每分钟可完成以下两个行动之一：
- 移动到距离当前坐标 \(1\) 单位的位置。
- 在当前坐标处的设施中，选择一个未检查的项目进行检查。
安全检查结束时，所有设施的所有检查项目必须至少由一名工人检查过。求出完成所有安全检查所需的最短时间。
$ 1 \le N \le 10^5 \(，\) 1 \le K \le 10^9 \(，\) 1 \le A_i,B_i \le 10^9 $。保证 \(A\) 递增。
首先显然可以二分 + 验证，那么问题就变为，如何验证在 \(x\) 分钟内，是否可以完成任务。
考虑贪心策略。观察样例，一种自然的想法是：一个人 \(A\) 先去后面，让另一个人 \(B\) 自己在当前位置干，并且 \(B\) 以后都不用去后面了，尽量让两个人同时在两个地方完成自己所在位置的任务。另外就是，工人是不会走回头路的，这样一定不优。
考虑计算所需的总时间，每个工作都需要被做，时间为 \(\sum_iB_i\)，剩余的需要最小化的时间就是工人花费在路上的时间。
先考虑对每一个工人计算答案，其花费在路上的时间就是他最远走到的（也是最后检查的）设施的坐标。
简单手模样例 4，发现安排工人的关键在于最后，我们可以考虑从后往前安排。由于我们已经钦定了总时间 \(x\)，不妨令第一个人到达了 \(A_i\)，那么他还剩 \(x-A_i\) 的时间去检查项目。于是贪心地让他检查 最靠后的 \(x-A_i\) 个项目 即可，这样就尽量让其他人不用来后面了，可以使总时间达到最优。
然而这道题不能对每个人都这样安排，因为 \(K\) 太大了，我们考虑让多个人捆绑在一起进行工作。从后往前扫，如果需要做的工作 \(S\)（\(B\) 的后缀和）大于当前派遣到 \(>A_i\) 位置的工人的总贡献 \(C\)（\(x-A_j\) 之和，其中 \(j\) 为工人派往的位置），那么就新增 \(\lceil(S-C)/(x-A_i)\rceil\) 名工人到 \(A_i\)。
具体见代码实现。时间复杂度 \(O(N\log\sum B_i)\)。
#include <bits/stdc++.h>
#define f(i, a, b) for (int i = (a); i <= (b); ++i)
#define g(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;void solve() {int n, k; cin >> n >> k;vi a(n + 1), b(n + 1);f(i, 1, n) cin >> a[i]; f(i, 1, n) cin >> b[i];vl s(n + 1); s[n] = b[n]; g(i, n - 1, 1) s[i] = s[i + 1] + b[i];auto check = [&](ll T) -> bool {ll w = 0; // used workersll c = 0; // workers total contributiong(i, n, 1) {if (c < s[i]) {// need new workersll need = s[i] - c;ll contrib = T - a[i]; // contribution of a worker who arrives at a[i]if (contrib <= 0) return false;ll cnt = (need + contrib - 1) / contrib; // number of workers needed (ceiling)w += cnt;if (w > k) return false;c += cnt * contrib;}}return true;};ll l = a[n], r = a[n] + s[1], mid;while (l + 1 < r) {mid = l + r >> 1;if (check(mid)) r = mid;else l = mid;}cout << r << '\n';return;
}signed main() {cin.tie(0)->sync_with_stdio(false);int tt = 1;// cin >> tt;while (tt--) solve();return 0;
}