NC20215. [JSOI2015]套娃
描述
输入描述
第一行包含一个正整数N。接下来N行，每行包含三个正整数Outi,Ini,Bi，表示i号套娃的外径，内径，以及好看度。N ≤ 2∗10^5,1 ≤ Ini < Outi ≤ 10^4,1 ≤ Bi ≤ 10^9
输出描述
输出文件包含一行一个整数，表示不满意度的最小值
示例1
输入:
3 5 4 1 4 2 2 3 2 1
输出:
7
C++11(clang++ 3.9) 解法, 执行用时: 250ms, 内存消耗: 12260K, 提交时间: 2020-03-28 22:58:54
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
struct miku
{
int in,out,b;
}a[200010];
multiset<int>s;
multiset<int>::iterator it;
int n;
ll ans;
bool cmp(miku a,miku b)
{
return a.b>b.b;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&a[i].out,&a[i].in,&a[i].b);
ans+=1ll*a[i].in*a[i].b;
s.insert(a[i].out);
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++)
{
it=s.lower_bound(a[i].in);
if(it!=s.begin())
{
it--;
ans-=1ll*a[i].b*(*it);
s.erase(it);
}
}
printf("%lld",ans);
}