What is the most stressful aspect of the CF1132D training program?

本文共计1364个文字，预计阅读时间需要6分钟。

题目链接+题目+链接：题解方法一+知识点：贪心，优先队列，二分。题解方法二+知识点：自然，二分。显然，这道题可以用二分解答。check函数可以使用小根堆，维持时间最短的先充电。但优化这道题会炸。

题目链接

题目

见链接。

题解 方法一

知识点：贪心，优先队列，二分。

显然，这道题可以用二分答案做。check 函数可以用小根堆，让维持时间最小的先充电。

但是不优化这道题会炸。有两个关键优化：一个是快读快写能省不少时间，还有一个是把维持天数当一个变量存起来以免重复运算浪费时间。其他一些小优化：用 pop 把元素弹出代替析构函数自己初始化能省一点时间，只让天数小于 \(k\) 的电脑入队，每次充完电检测维持天数小于 \(k\) 的才重新入队。优化前是超 \(3\) 秒限制的，优化后是 \(1.5\) 秒还算可以。

时间复杂度 \(O((n+k)\log n)\) ，常数应该在 \((100,1000)\)

空间复杂度 \(O(n)\)

方法二

知识点：贪心，二分。

方法一的检验并非正解，其实有一个更妙的方法去验证电脑是否会在 \(k\) 天之前关机。

我们用一个数组 \(cnt[i]\) 表示有多少电脑最晚第 \(i\) 天前要充一次电。比如一台电脑是初始电量是 \(20\) 每天耗电 \(15\) 要维持到 \(8\) 天，每次充电 \(40\) ，那么它最晚在第 \(2\) 、\(5\)、\(7\) 天要充一次电，于是 \(cnt[\{2,5,7\}]\) 都要加一。

我们不关心电脑在哪天充电，我们只关心电脑最晚要在什么时候前充电，所以 \(cnt[i]\) 在某些天超过 \(1\) 是可行的。因为既然我们知道在这天之后有三台电脑会关机，只要在这天之前什么时候充电都行，不过要满足之前有空闲的天数。

于是，现在我们把它从 \(1\) 到 \(i\) 累和，得到一个结果 \(sum\) ，表示到 \(i\) 天要至少要充几次电，显然每天只能充一次，那么如果 \(sum > i\) ，则存在电脑没在最晚时间前充上电，关机了，是这个答案是不可行的。如果 \(sum \leq i\) ，说明到第 \(i\) 天充电次数完全够用，可以继续。

时间复杂度 \(O(n+k)\) ，常数在 \((50,200)\)

空间复杂度 \(O(n+k)\)

代码 方法一

#include <bits/stdc++.h> #define ll long long using namespace std; inline ll read() { ll x = 0, f = 1; char c = getchar(); while (c < '0' || c>'9') { if (c == '-') f = -1; c = getchar(); }///整数符号 while (c >= '0' && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }///挪位加数 return x * f; }///关键优化，快读 struct node { ll a, b, v;///关键优化，存储天数 bool operator>(const node &x) const {///大根堆重载小于，小根堆重载大于,true代表优先级小,必须是常函数或者友元函数 return v > x.v; } }a[200007]; int n, k; // struct cmp { // bool operator()(const node &a, const node &b) { // return a.a / a.b > b.a / b.b; // } // } ///也可以写个比较类 priority_queue<node, vector<node>, greater<node>> pq; //priority_queue<node, vector<node>, cmp> pq; bool check(ll mid) { while (!pq.empty()) pq.pop();///优化 for (int i = 0;i < n;i++) if (a[i].v < k)pq.push(a[i]); ///优化 for (int i = 1;i <= k;i++) { if (pq.empty()) return true; node x = pq.top(); pq.pop(); if (x.v < i) return false;///加之前判断是否能撑到这个时候 x.a += mid; x.v = x.a / x.b + 1; if (x.v < k) pq.push(x);///优化 } return true; } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); n = read(); k = read(); for (int i = 0;i < n;i++) a[i].a = read(); for (int i = 0;i < n;i++) a[i].b = read(), a[i].v = a[i].a / a[i].b + 1;///因为一天结束才扣电，而到了这天就算，所以取下整能过几天，加一是往后一天也算到了。 ll l = 0, r = 2e12; while (l <= r) { ll mid = l + r >> 1; if (check(mid)) r = mid - 1; else l = mid + 1; } cout << (l > 2e12 ? -1 : l) << '\n'; return 0; } 方法二

#include <bits/stdc++.h> #define ll long long using namespace std; int n, k; ll a[200007], b[200007]; bool check(ll mid) { int r = k; vector<int> sum(k); for (int i = 0;i < n;i++) { ll tmp = a[i]; while (tmp / b[i] + 1 < k && r >= 0) { sum[tmp / b[i] + 1]++; tmp += mid; r--; } if (r < 0) return false; } for (int i = 1;i < k;i++) { sum[i] += sum[i - 1]; if (sum[i] > i) return false;///充电次数超过天数，不可能实现 } return true; } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> n >> k; for (int i = 0;i < n;i++) cin >> a[i]; for (int i = 0;i < n;i++) cin >> b[i]; ll l = 0, r = 2e12; while (l <= r) { ll mid = l + r >> 1; if (check(mid)) r = mid - 1; else l = mid + 1; } cout << (l > 2e12 ? -1 : l) << '\n'; return 0; }