题解:
每一次不能满足的时候
找一个之前有过的
然后最小的
和他替换
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=;
long long ans;
int x[N],y[N],l,f[N],n,d[N];
void down(int x)
{
int i=x;
if (x*<=l&&d[x*]<d[x])i=x*;
if (x*<l&&d[x*+]<d[i])i=x*+;
if (i!=x)
{
swap(d[i],d[x]);
down(i);
}
}
void up(int x)
{
if (x==)return;
if (d[x]<d[x/])
{
swap(d[x],d[x/]);
up(x/);
}
}
int cmp(int a,int b)
{
return x[a]<x[b];
}
int main()
{
scanf("%d",&n);
for (int i=;i<=n;i++)scanf("%d%d",&x[i],&y[i]),f[i]=i,x[i]=min(x[i],n);
sort(f+,f+n+,cmp);
for (int i=;i<=n;i++)
{
d[++l]=y[f[i]];
up(l);
ans+=y[f[i]];
if (x[f[i]]<l)
{
ans-=d[];
d[]=d[l--];
down();
}
}
printf("%lld\n",ans);
}