自动搬运

查看原文

来自洛谷，原作者为

	FjswYuzu Rainybunny狂热粉丝!111111 | Last Goodbye

搬运于2025-08-24 22:17:20，当前版本为作者最后更新于2020-02-13 16:38:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\ \ \ \ \ \ \$算是贪心基础吗？

$\ \ \ \ \ \ \$我们假设这 $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）当中，计算初始答案（也就是全部都是空套娃的情况）。

$\ \ \ \ \ \ \$然后用二分查找（lower_bound）找到第一个大于等于当前考虑套在一起的套娃内径的外径。因为还是装不下，所以迭代器减一，然后将这两个娃套在一起，将这个套娃从可重集中去掉（可重集内部元素递增），并减去相应的贡献。

$\ \ \ \ \ \ \$特殊的，如果迭代器没有查找到，也就是返回了 Set.begin()，此时当前的套娃没有一个满足要求。

$\ \ \ \ \ \ \$有了这些，思路就很清晰了。注意套娃可能一样，所以要用可重集。

#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
#define int LL
typedef multiset<int>::iterator Site;
struct tw{
	int out,in,b;
	bool operator < (tw q) const {return b>q.b;}
}wa[200005];
multiset<int> Set;
signed main(){
	int n,ans=0;
	scanf("%lld",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%lld %lld %lld",&wa[i].out,&wa[i].in,&wa[i].b);
		ans+=wa[i].in*wa[i].b;
		Set.insert(wa[i].out);
	}
	sort(wa+1,wa+1+n);
	for(int i=1;i<=n;++i)
	{
		Site it=Set.lower_bound(wa[i].in);
		if(it!=Set.begin())	ans-=(*--it)*wa[i].b,Set.erase(it);
	}
	printf("%lld",ans);
	return 0;
}

$\ \ \ \ \ \ \$劝诫：禁止套娃。