P6093 [JSOI2015] 套娃 题解

思路

我们假设这 $n$ 个套娃全部空置，我们的答案是 $\sum_{i = 1}^{n} in_{i} \times b_{i}$。在当前情况下，如果我们再将一个套娃放进另一个套娃（不妨设为 $i$ 和 $j$），不满度就减少了 $out_{i} \times b_{j}$。想到这，考虑到 $in$，$out$，$b$ 是不会改变的，同时外径大的套娃也不会影响其他套娃，可以考虑贪心。

贪心策略：先以 $b_{i}$ 为关键字对 $n$ 个套娃从大到小排序，按着顺序将 $out$ 最大的套娃套进去。

接下来证明一下这个贪心策略。

设两个套娃分别是 $i$ 和 $j$。如果 $b_{i} > b_{j}$，$out_{p} > out_{q}$，很显然，有 $b_{i} \times out_{q} + b_{j} \times out_{p} < b_{i} \times out_{p} + b_{j} \times out_{q}$，证明了我们的贪心策略是正确的。

回到问题，我们现在要做的就是匹配两个套娃，首先将所有套娃扔进一个 multiset 当中，计算初始答案，也就是全部都是空套娃的情况。

然后用二分查找找到第一个大于等于当前考虑套在一起的套娃内径的外径。因为还是装不下，所以迭代器减一，然后将两个套娃套到一起，将这个套娃从 multiset 中去掉，并减去相应的贡献。

特殊的，如果迭代器里没有找到，也就是它返回了第一项，此时当前的套娃没有一个符合要求。

还有，由于套娃是可以重复的，所以不能只用 set，而是要用 multiset。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e6 + 5;
multiset <ll> st;
struct node {
	ll x, y, z;
}a[N];
bool cmp(node x, node y) {
	return x.z > y.z;
}
int main() {
	ll n;
	cin >> n;
	ll ans = 0;
	for(ll i = 1; i <= n; i++) {
		cin >> a[i].x >> a[i].y >> a[i].z;	
		ans += a[i].y * a[i].z;
		st.insert(a[i].x);
	}
	sort(a + 1, a + n + 1, cmp);
	for(ll i = 1; i <= n; i++) {
		multiset <ll> :: iterator tmp;
		tmp = st.lower_bound(a[i].y);
		if(tmp != st.begin()) {
			ans -= (*(--tmp)) * a[i].z;
			st.erase(tmp);
		}
	}
	cout << ans << endl;
	return 0;
}

后记

求管理员通过，管理员辛苦了。

如果这篇题解对你有帮助，不妨点个赞再走吧。