前言

转载请将本段放在文章开头显眼处，如有二次创作请标明。
原文链接：https://www.codein.icu/cf1374e2/

前言2

本题为 CF1374E1 的 Hard Version，题意变化不大，解法也是在其基础上优化，因此如果没有做过的话，建议先做 CF1374E1，或者简单看看 我的博客 中的题解。

题意

每本书都有权值，每本书可能被 A 喜欢，可能被 B 喜欢，要求选出的书中，A 与 B 都至少喜欢 $k$ 本，且最少选出 $m$ 本书，求最小权值和。

相对于 Easy Version，只有一个限定条件的变化：最少选出 $m$ 本书。

解法

依然给书分类：

1. A 与 B 都不喜欢
2. B 喜欢
3. A 喜欢
4. A 与 B 都喜欢

考虑强制选定 $m$ 本书对做法产生什么影响。

设第3种中选出 $i$ 本书，则第1种、第2种中都需要选出 $k – i$ 本书。

设枚举到 $i$ 时，还需要选出的书本数为 $\texttt{need}$，更新其值：

1. $i \leq k$ 时，选出了 $i + 2 \times (k – i)$ 本书，即 $k \times 2 – i$ 本书，还需要 $m – k \times 2 + i$ 本书。
2. $i > k$ 时，选出了 $i$ 本书，还需要 $m – i$ 本书。

所需的书在第0种、第1种未被选择部分、第2种未被选择部分选出。

由于枚举在第3种中选择 $i$ 本书，因此无需考虑在第3种中再次选择。

考虑选择范围：

1. 全部可选
2. $[k – i + 1,R]$ 可选
3. $[k – i + 1,R]$ 可选

在该范围内选出 $\texttt{need}$ 本书，可以维护一个大小为 $\texttt{need}$ 的set，在加入、弹出元素时更新 $\texttt{sum}$ 值来维护权值和大小。

由于枚举 $i$ 单调递增，第1种、第2种中可选范围不断扩大，向set中插入元素进行维护。

$\texttt{need}$ 值也会变化，因此可以维护一个可选set以存放可选的元素。

记选择set为 $\texttt{choose}$，可选set为 $\texttt{all}$。

考虑用 $\texttt{all}$ 更新 $\texttt{choose}$ 的过程：

1. $\operatorname{size}(\texttt{choose}) > \texttt{need}$，将其中最大元素转移到 $\texttt{all}$ 中。
2. $\operatorname{size}(\texttt{choose}) < \texttt{need}$，将 $\texttt{all}$ 中最小元素转移到其中。
3. $\operatorname{size}(\texttt{choose}) = \texttt{need}$，比较 $\texttt{all}$ 中最小元素与 $\texttt{choose}$ 中最大元素，若 $\texttt{all}$ 中最小元素更小则进行交换。

由于不能保存取得答案时的状态，则保存取得答案时的 $i$ 值，再次运行到后输出所选书号。

代码

也可以看官方的代码。

#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;
template <typename T>
void read(T &r)
{
    static char c; r = 0;
    for (c = getchar(); c > '9' || c < '0'; c = getchar());
    for (; c >= '0' && c <= '9'; r = (r << 1) + (r << 3) + (c ^ 48), c = getchar());
}
const int maxn = 2e5 + 100;
int n, m, k;
struct node
{
    int t, id;
    bool operator<(const node &b) const { return t == b.t ? id < b.id : t < b.t; }
} A[4][maxn];
int num[4];
long long sums[4][maxn];
inline void init()
{
    read(n), read(m), read(k);
    for (int i = 1; i <= n; ++i)
    {
        int t, a, b, p;
        read(t), read(a), read(b), p = a * 2 + b;
        A[p][++num[p]].id = i, A[p][num[p]].t = t;
    }
    for (int i = 0; i < 4; ++i) sort(A[i] + 1, A[i] + 1 + num[i]);
    for (int i = 0; i < 4; ++i)  for (int j = 1; j <= num[i]; ++j) sums[i][j] = sums[i][j - 1] + A[i][j].t;
}
set<node> all, choose;
int sum, need;
inline void updateChoose()
{
    if (need < 0) need = 0;
    set<node>::iterator it;
    while (choose.size() > need) it = --choose.end(), sum -= it->t,all.insert(*it), choose.erase(it);
    while (choose.size() < need && !all.empty()) sum += (it = all.begin())->t,choose.insert(*it), all.erase(it);
    while (!choose.empty() && !all.empty() && (it = --choose.end())->t > all.begin()->t)
    {
        sum -= it->t, sum += all.begin()->t;
        all.insert(*it), choose.erase(it);
        choose.insert(*all.begin()), all.erase(all.begin());
    }
}
inline void updateRange(int i)
{
    if(k - i >= 0)
    {
        need = m - k * 2 + i;
        if(k - i + 1 <= num[1]) all.insert(A[1][k - i + 1]);
        if(k - i + 1 <= num[2]) all.insert(A[2][k - i + 1]);
    }
    else need = m - i;
}
int main()
{
    init();
    int start = 0;
    while (start <= num[3] && (k - start > num[1] || k - start > num[2] || m - start - (k - start) * 2 < 0)) ++start;
    if (start == num[3] + 1) { puts("-1"); return 0; }
    for (int i = 0; i < 3; ++i) for (int j = num[i]; j > (i == 0 ? 0 : k - start); --j) all.insert(A[i][j]);
    long long ans = 1ll << 60;
    int ansp = -1;
    for (int i = start; i <= num[3]; ++i)
    {
        updateRange(i),updateChoose();
        int res = sums[3][i] + sum;
        if (k - i >= 0) res += sums[1][k - i] + sums[2][k - i];
        if (res < ans && ((k - i >= 0) ? (i + 2 * (k - i) + choose.size() == m) : (i + choose.size() == m))) ans = res, ansp = i;
    }
    printf("%lld\n", ans);
    all.clear(), choose.clear();
    for (int i = 0; i < 3; ++i) for (int j = num[i]; j > (i == 0 ? 0 : k - start); --j) all.insert(A[i][j]);
    for (int i = start; i <= num[3]; ++i)
    {
        updateRange(i),updateChoose();
        if (i == ansp)
        {
            for (int j = 1; j <= i; ++j) printf("%d ", A[3][j].id);
            if (k - i > 0) for (int j = 1; j <= k - i; ++j) printf("%d %d ", A[1][j].id, A[2][j].id);
            for (set<node>::iterator it = choose.begin(); it != choose.end(); ++it) printf("%d ", it->id);
            return 0;
        }
    }
    puts("-1");
    return 0;
}