题目描述

难度分:$2133$

输入$T(\leq 10^5)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$。然后输入$n$行，每行输入三个数$k_i(1 \leq k_i \leq n)$、$l_i(1 \leq l_i \leq 10^9)$、$r_i(1 \leq r_i \leq 10^9)$。

有$n$只骆驼，你需要把这$n$只骆驼按照某种顺序，排成一行。如果第$i$只骆驼在前$k_i$个位置中，那么它的幸福值是$l_i$，否则是$r_i$。输出总幸福值的最大值。

输入样例

3
2
1 5 10
2 15 5
3
2 93 78
1 71 59
3 57 96
19
19 23 16
5 90 13
12 85 70
19 67 78
12 16 60
18 48 28
5 4 24
12 97 97
4 57 87
19 91 74
18 100 76
7 86 46
9 100 57
3 76 73
6 84 93
1 6 84
11 75 94
19 15 3
12 11 34

输出样例

25
221
1354

算法

反悔贪心

$l \gt r$的骆驼放在$l \lt r$的骆驼的左边是更优的（可以用交换法证明）。所以把$l \gt r$的骆驼分成一组，其余骆驼分成另一组，两组互相独立，分别计算。

下面以$l \gt r$为例进行说明：

可以先把所有$r$加起来，然后讨论$l-r$怎么选取？即怎么选一些$r$换成$l$？如果没法把骆驼放在前$k$个中，那么幸福值只能是$r$，这相当于不选$l-r$。

按照$k$从小到大排序。采取「捡到西瓜，丢掉芝麻」的反悔贪心策略：先把$l-r$入堆（最小堆），如果入堆后发现堆的大小超过当前的$k$，则弹出堆顶的「芝麻」。

复杂度分析

时间复杂度

实现的时候其实并不需要对$O(n)$个骆驼进行排序，只需要把$l \gt r$的骆驼放在前面，将$k$作为索引即可（$l \leq r$的骆驼用$n-k$作为索引），因此这个过程的时间复杂度为$O(n)$。可以得到两个组$a$和$b$，其中$a[k]$是$l \gt r$的骆驼的$l-r$列表，$b[n-k]$是$l \leq r$的骆驼的$r-l$列表。之后两个组需要遍历$a$和$b$中的列表，总共有$O(n)$个元素，在最差情况下需要进行反悔操作，元素入堆的时间复杂度为$O(log_2n)$，总的时间复杂度为$O(nlog_2k)$，这也是整个算法的时间复杂度瓶颈。

空间复杂度

$a$和$b$中的元素总个数为$O(n)$；反悔堆$heap$中的元素个数在最差情况下也为$O(n)$；因此整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

void solve(vector<vector<int>>&camels) {
    int n = camels.size();
    LL ans = 0;
    vector<vector<int>> a(n + 1, vector<int>()), b(n, vector<int>());
    for(int i = 0; i < n; i++) {
        int k = camels[i][0], l = camels[i][1], r = camels[i][2];
        if(l > r) {
            ans += r;
            a[k].push_back(l - r);
        }else {
            ans += l;
            b[n - k].push_back(r - l);
        }
    }
    function<void(vector<vector<int>>&)> f = [&](vector<vector<int>>& a) {
        priority_queue<int, vector<int>, greater<int>> heap;
        for(int k = 0; k < a.size(); k++) {
            for(int d: a[k]) {
                ans += d;
                heap.push(d);
                if(heap.size() > k) {
                    ans -= heap.top();
                    heap.pop();
                }
            }
        }
    };
    f(a);
    f(b);
    printf("%lld\n", ans);
}

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        int n;
        scanf("%d", &n);
        vector<vector<int>> camels;
        for(int i = 0; i < n; i++) {
            int k, l, r;
            scanf("%d%d%d", &k, &l, &r);
            camels.push_back({k, l, r});
        }
        solve(camels);
    }
    return 0;
}