POJ Supermarket

贪心+结构体排序

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

inline int read(){
	int ret=0,f=1;
	char c=getchar();
	for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-f;
	for(;c>='0'&&c<='9';c=getchar()) ret=ret*10+c-'0';
	return ret*f;
}

const int maxn=1e5+55;

int n,ans;
bool vis[maxn];
struct cow{
	int p,d;
}c[maxn];

bool cmp(cow _x,cow _y){
	return _x.p>_y.p;
}

signed main(){
	
	while(cin>>n){
		memset(vis,0,sizeof(vis));//多测清空！！！！！ 
		for(int i=0;i<n;i++){
//			c[i].p=read();c[i].d=read();
			cin>>c[i].p>>c[i].d;
		}
		sort(c,c+n,cmp);
		int res=0;
		for(int i=0;i<n;i++){
			for(int j=c[i].p;j>=0;j--){
				if(j==0){
					break;
				}
				if(vis[j]==0){
					vis[j]=1;
					res+=c[i].d;
					break;
				}
			}
		}
		
		cout<<res<<endl;
	}
	
	return 0;
}