贪心杂题

P4698 [CEOI 2011] Hotel

有 \(n\) 个房间和 \(m\) 个订单，每个房间有容量 \(p_i\) 和成本 \(c_i\)，每个订单有人数 \(d_i\) 和租金 \(v_i\)。同一个订单必须安排在同一个房间内，订单的人数不得超过房间的容量。问如果完成不超过 \(o\) 个订单，租金之和减去成本之和的最大值。

保证：对于 \(\forall p_{j_1}<p_{j_2},\ c_{j_1}\le c_{j_2}\)。

\(n,m\le 5\times 10^5,\ p_i,c_i,d_i,v_i\le 10^9\)

如果不考虑冲突的情况，每个订单肯定选择能住下且最便宜的一间房间。而对于两个订单都想住同一间房间的情况，我们一定会让租金多的优先住便宜的。

因此有贪心策略：按租金从大往小处理订单，每个订单选择最便宜的一件住下。然后计算每个订单带来的收益，从大到小取前 \(o\) 大的即可。

P4785 [BalticOI 2016] 交换 (Day2)

P5021 [NOIP 2018 提高组] 赛道修建

给定一棵树，边有边权。你需要选出 \(m\) 条没有公共边的链，使得链长度的最小值最大。问最大值。

\(n\le 5\times 10^4,\ m\le n-1\)

首先二分答案，问题转化为选一些长度不低于 \(mid\) 的链，问最多选几条。

对于当前节点 \(u\)，考虑以 \(u\) 为 \(\operatorname{lca}\) 的路径：如果它们破坏了子树内部的局部最优解，那么显然不优，因为不会增加链的数量。因此我们对每棵子树求出其内部的最优解，以及在不破坏局部最优解的前提下，从根出发的最长链。然后考虑合并这些链，先将所有链进行排序，然后按长度从小到大考虑，每次从剩余集合中拿出长度不低于 \(mid-x\) 且最短的一条路径，并删去二者；若不存在则直接跳过。

显然这种方法可以得到子树内最优解（只需证明一次匹配之后子问题的最优解只会 \(-1\)），并且容易证明剩余的最长链也一定取到最大值（因为不可能调整，也不可能创建新的匹配）。上面的集合使用 multiset 维护即可。时间复杂度 \(O(n\log^2n)\)。

代码

#include<iostream>
#include<set>
#include<random>
using namespace std;
const int N = 5e4 + 10;

struct Edge {
    int v, w, next;
} pool[2 * N];
int ne, head[N];

void addEdge(int u, int v, int w) {
    pool[++ne] = {v, w, head[u]};
    head[u] = ne;
}

int n, m, res;
int lim;

multiset<int> st;
int f[N];

void dfs(int u, int fa) {
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(v == fa) continue;
        dfs(v, u);
    }
    st.clear();
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v, w = pool[e].w;
        if(v == fa) continue;
        if(f[v] + w >= lim) ++res;
        else st.insert(f[v] + w);
    }
    for(auto it = st.begin(); it != st.end(); ) {
        auto x = it;
        auto y = st.lower_bound(lim - *x);
        if(x == y) ++y;
        if(y == st.end()) { ++it; continue; }
        if(*x + *y < lim) break;
        ++it;
        if(it == y) ++it;
        st.erase(x);
        st.erase(y);
        ++res;
    }
    f[u] = st.empty() ? 0 : *st.rbegin();
}

bool check() {
    res = 0;
    dfs(1, 0);
    return res >= m;
}

mt19937 rng((random_device){}());

int main() {

    cin >> n >> m;
    for(int i = 1; i <= n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
        addEdge(v, u, w);
    }

    int l = 0, r = 0x3f3f3f3f;
    while(l < r) {
        int mid = (l + r + 1) >> 1;
        lim = mid;
        if(check()) {
            l = mid;
        } else r = mid - 1;
    }

    cout << l << '\n';

    return 0;
}

P11820 [PA 2015] 健身房 / Siłownia

我们尽可能推迟每次有人健身的时刻，才可能让一次健身覆盖尽可能多的人。也就是说，如果当前不一定要有人健身，就继续推迟到后面。只有时间卡在某个人的截止时间上时，才进行健身。

对于多个人使用一个健身器材的情况，若他们截止时间相同，将会被放到一个时刻处理，从而误判为无解。对于这种情况，我们可以选择一个人，将它的截止时间提前。显然提前 \(l\) 较小的人更优。若出现某个人的截止时间被提前到了开始时间之前，则直接报告无解。

P8365 [LNOI2022] 吃

有一个变量 \(x\) 初始等于 \(1\)。给定 \(n\) 个二元组 \((a_i,b_i)\)，你需要进行 \(n\) 次如下操作：

选择一个之前没有选过的二元组，将 \(x\gets x\times a_i\) 或 \(x\gets x+b_i\)；

问最终 \(x\) 的最大值。

\(n\le 5\times 10^5\)

应该算性质题，但是不管了就放这里了。

首先，如果我们决定了每个二元组是进行加法还是乘法，那么我们把加法都放在前面肯定是最优的。

直觉上乘法比加法优，但是 \(a_i=1\) 时不是。而此时我们一定会选择加法，因此可以先特判掉，直接累加到 \(x\) 上。其余情况 \(a_i\ge 2\)，至少翻一倍。对于前面加法的部分，如果我们只保留最大的一个，将其它都换为 \(\times 2\) 一定会更优。因此除去 \(a_i=1\) 的部分加法最多进行一次。

P11361 [NOIP2024] 编辑字符串

给定两个长为 \(n\) 的 01 串 \(s_1,s_2\)，两个串各有一些区间是“可交换的”。你可以任意重排每个区间的字符。问 \(\sum [s_{1,i}=s_{2,i}]\) 的最大值是多少。

\(n\le 10^5\)

对于这种不带权的问题，能匹配则匹配显然是不劣的，因为一次匹配不会拆分超过一对匹配。

P3294 [SCOI2016] 背单词

给你一棵 Trie 树（根节点是节点 \(0\)），你需要找出它的一个拓扑序 \(p\)（从 \(0\) 开始编号），最小化 \(\sum_{i=1}^{n}p[i]-p[fa[i]]\)。

\(\sum |s_i|\le 5.1\times 10^5\)

咕咕咕

贪心 杂题

贪心杂题