题解 P6093 【[JSOI2015]套娃】
FjswYuzu
·
·
题解
---
$\ \ \ \ \ \ \ $我们假设这 $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()`，此时当前的套娃没有一个满足要求。
---
$\ \ \ \ \ \ \ $有了这些，思路就很清晰了。注意套娃可能一样，所以要用可重集。
```cpp
#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;
}
```
---
$\ \ \ \ \ \ \ $~~劝诫：禁止套娃。~~