题解 CF1374E2 【Reading Books (hard version)】

sdxjzsq

2021-04-20 05:13:24

Solution

### 题目链接 [https://www.luogu.com.cn/problem/CF1374E2](https://www.luogu.com.cn/problem/CF1374E2) [https://codeforces.com/contest/1374/problem/E2](https://codeforces.com/contest/1374/problem/E2) ### 题目大意 在 $n$ 本书中选出 $m$ 本,使得至少有 $k$ 本 Alice 喜欢、有 $k$ 本 Bob 喜欢,并且总阅读时间最小。 ### 思路 在 [CF1374E1](https://www.luogu.com.cn/problem/CF1374E1) 中,我们可以~~很显然地~~看出直接用贪心即可 AC。根据CF比赛E1与E2一脉相承的传统,我们可以认为这题也可以用贪心来做,区别是本题增加了恰好读 $m$ 本的限制,这就导致不能像 E1 那样无脑贪心地选时最少的书来读,但这并不妨碍我们贪心。 首先对书的性质进行分类: - $00:$ Alice 和 Bob 都不喜欢 - $01:$ Alice 喜欢, Bob 不喜欢 - $10:$ Alice 不喜欢, Bob 喜欢 - $11:$ Alice 和 Bob 都喜欢 因为肯定希望优先阅读花费时间更少的书,因此我们可以使用4个优先队列维护上述4类不同的书。 分好类之后,我们像 E1 那样先在 $11$类 和 $01+10$类 中优先选择阅读时间更少的书,直到满足 Alice 和 Bob 喜欢的书都至少有 $k$ 本这一条件,记录当前 $m$ 的消耗情况。为了之后方便调整,我选择将选出来的书从优先队列中弹出,并加入对应的四个答案优先队列中,但将花费时间最长的书放在堆顶(后面将叙述为什么这么做)。 满足第一个要求后,便分为以下三种情况: 1. 如果选出的书数量恰好为 $m$,那么直接输出当前答案即可,因为这已经满足了阅读时间最短。 2. 如果选出的书数量大于 $m$,那么说明 $01+10$类选择地太多,将 1 本 $01+10$类 换成 $11$类 可以在满足“两人都至少有 $k$ 本喜欢”的情况下减少 1 本书。因此我们不断将 $01+10$类 换为 $11$类 直到数量等于 $m$ 即可。如果发现 $11$类 的书不够用或者答案队列中已经没有 $01+10$ 类 的书,那么可以判定无解。 3. 如果选出的书数量小于 $m$,那么说明还需要更多的书。在这种情况下我们有两种选择:一是将 $11$类 的书换为 $01+10$类 的书,这样可以在满足要求的情况下增加 1 本选出的数量;二是在四类书中选择用时最短的一本直接加入答案队列中。 为了保证总阅读时间最小,我们需要从上述两种选择中选出用时较少的一种方案,这里的用时比较难找出:对于第一种选择,对答案的增量为 “ $01+10$类书的最小用时” 减去 “答案序列中 $11$类书的最长用时”;而对于第二种选择,对于答案的增量为 “四类书中的最小用时”。将这两个用时增量都求出选择用时短的那个即可。 需要注意的是可能有的种类书的数量不够当前操作,需要提前判断优先队列是否为空(似乎用数组会比优先队列好写?) ~~(我感觉前面整个过程都保证了贪心的正确性,不证自明,证明略)~~ 上述过程中,我们对优先队列最多执行 $O(n)$ 次操作,而优先队列每次插入与弹出操作时间复杂度为 $O(\log n)$,因此总复杂度为 $O(n\log n)$。 当然,上述操作中的优先队列可以改为数组+预处理排序实现,但预处理复杂度 $O(n\log n)$,和优先队列复杂度相差不大。 我的方法和官方不同的是,不需要枚举在 $11$类 书中选择多少本,因此~~可能~~导致了常数上的提升(G++17下我的代码171ms,官方题解592ms,本题洛谷上的另外一篇题解280ms) ### code ``` cpp #include <cstdio> #include <queue> using namespace std; const int maxn = 2e5 + 7; int n, m, k, tot, tmp[4], flag = 1; struct node { int no, t; bool operator<(const node &rhs) const { return t > rhs.t; } }; priority_queue<node> book[4], ans[4]; int switchD(int v) { node x = book[v].top(); tot += x.t, x.t = -x.t; ans[v].push(x), book[v].pop(); --m; } int switchR(int v) { node x = ans[v].top(); tot += x.t, x.t = -x.t; book[v].push(x), ans[v].pop(); ++m; } int main() { scanf("%d%d%d", &n, &m, &k); for (int i = 1, t, a, b; i <= n; ++i) scanf("%d%d%d", &t, &a, &b), book[a << 1 | b].push({i, t}); while (k-- && flag) { for (int i = 1; i < 4; ++i) tmp[i] = !book[i].empty(); if ((tmp[1] + tmp[2] < 2) && tmp[3]) switchD(3); // 01或10类书的数量不够 else if ((!tmp[3]) && tmp[1] && tmp[2]) switchD(1), switchD(2); // 11类书的数量不够 else if (tmp[3] + tmp[2] + tmp[1] == 3) if (book[1].top().t + book[2].top().t > book[3].top().t) switchD(3); // 11类比01+10类用时短 else switchD(1), switchD(2); // 11类比01+10类用时长 else flag = 0; // 无解的情况下将flag置0 } while (m < 0 && flag) { tmp[1] = !ans[1].empty(), tmp[2] = !ans[2].empty(), tmp[3] = !book[3].empty(); if (tmp[1] && tmp[2] && tmp[3]) switchR(1), switchR(2), switchD(3); // 当前答案本数大于m,将01+10类换成11类 else flag = 0; } while (m > 0 && flag) { int now = -1, v = 1e9; for (int i = 0; i < 4; ++i) if ((!book[i].empty()) && v > book[i].top().t) now = i, v = book[i].top().t; tmp[1] = !book[1].empty(), tmp[2] = !book[2].empty(), tmp[3] = !ans[3].empty(); if (tmp[1] && tmp[2] && tmp[3] && v - ans[3].top().t > book[2].top().t + book[1].top().t) switchD(1), switchD(2), switchR(3); // 如果当前 11类 换 01+10类 选择用时更短 else if (now == -1) // 找不到可以换或者加入答案队列中的书 flag = 0; else switchD(now); } printf("%d\n", flag ? tot : -1); for (int i = 0; i < 4 && flag; ++i) while (!ans[i].empty()) printf("%d ", ans[i].top().no), ans[i].pop(); return 0; } ```