CF1374E2 Reading Books (hard version) 题解
本文最后更新于 199 天前,其中的信息可能已经有所发展或是发生改变。

前言

转载请将本段放在文章开头显眼处,如有二次创作请标明。
原文链接: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;
}
本文标题:CF1374E2 Reading Books (hard version) 题解
本文作者:Clouder
本文链接: https://www.codein.icu/cf1374e2/
转载请标明。
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇