题解 CF1374E2 【Reading Books (hard version)】

2021-04-20 05:13:24


题目链接

https://www.luogu.com.cn/problem/CF1374E2
https://codeforces.com/contest/1374/problem/E2

题目大意

在 $n$ 本书中选出 $m$ 本,使得至少有 $k$ 本 Alice 喜欢、有 $k$ 本 Bob 喜欢,并且总阅读时间最小。

思路

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

#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;
}