「JSOI2015」套娃

「JSOI2015」套娃

传送门

考虑贪心。

首先我们假设所有的套娃都互相不套。

然后我们考虑合并两个套娃 \(i\)，\(j\) 假设我们把 \(i\) 套到 \(j\) 里面去，那么就可以减少 \(b_j \times out_i\) 的花费。

我们有一种 贪心策略就是说把所有套娃按 \(b\) 从大到小排序，然后每次找一个 \(out\) 最大的让它套。

我们可以这么证明正确性：

对于四个套娃 \(i, j, k, l\) ，假设 \(b_i > b_j, out_k > out_l\) 且保证 \(i, j\) 都可以套 \(k, l\) ，

那么我们只需要证 \(b_i \times out_k + b_j \times out_l \ge b_i \times out_l + b_j \times out_k\) ，根据假设，这个式子显然成立。

那么我们就可以按照刚刚的策略贪心了。

具体来说就是用一个 multiset 维护所有的 \(out\) ，然后按 \(b\) 排序，每次在 multiset 里面 lower_bound 一个最大的 \(out\) 然后把相应的代价减掉。

需要特别注意的是：如果 \(in_i = out_j\) ，那么 \(i\) 是不能套 \(j\) 的。

参考代码：

#include <algorithm>

#include <cstdio>

#include <set>

#define rg register

#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

using namespace std;

template < class T > inline void read(T& s) {

    s = 0; int f = 0; char c = getchar();

    while ('0' > c || c > '9') f |= c == '-', c = getchar();

    while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();

    s = f ? -s : s;

}

typedef long long LL;

const int _ = 2e5 + 5;

int n; struct node { int in, out, b; } t[_];

inline bool cmp(const node& x, const node& y) { return x.b > y.b; }

multiset < int > s;

multiset < int > ::iterator it;

int main() {

#ifndef ONLINE_JUDGE

    file("cpp");

#endif

    read(n);

    LL ans = 0;

    for (rg int i = 1; i <= n; ++i) {

    	read(t[i].out), read(t[i].in), read(t[i].b);

    	ans += 1ll * t[i].b * t[i].in, s.insert(t[i].out);

    }

    sort(t + 1, t + n + 1, cmp);

    for (rg int i = 1; i <= n; ++i) {

    	it = s.lower_bound(t[i].in);

    	if (it != s.begin()) ans -= 1ll * t[i].b * (*--it), s.erase(it);

    }

    printf("%lld\n", ans);

    return 0;

}