很明显的贪心策略,先按权值排序,从过期时间向前遍历,给后面的权值插入创造更多的可能
遍历的过程用并查集减少时间。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define gc getchar()
using namespace std;
const int N=11000;
inline void qr(int &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
struct node{int d,t;bool operator <(const node a)const{return d>a.d;}}a[N];
int fa[N];
int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}
int main()
{
//freopen("a.in","r",stdin);
//freopen("a.out","w",stdout);
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)qr(a[i].d),qr(a[i].t);
for(int i=1;i<=10000;i++)fa[i]=i;
sort(a+1,a+n+1);int ans=0;
for(int i=1;i<=n;i++)
{
int t=get(a[i].t);
if(!t)continue;
ans+=a[i].d;
fa[t]=t-1;
}
printf("%d\n",ans);
}
return 0;
}
最后一次更新于2019-10-11
0 条评论