1910.cpp

HDOJ acm.hdu.edu.cn 第10卷的一些题目

//1910
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int DMAX = 10000;
const int LMAX = 100;
const int NMAX = 10000;
int n,l;
struct APP {
	int d;
	int p;
	bool operator < (const APP & at) const {
		if (p != at.p) return p > at.p;
		return d < at.d;
	}
}app[NMAX+10];
int get_val() {
	int ret = 0;
	char ch;
	while ((ch=getchar()) == ' ' || ch == '\n') ;
	if (ch == EOF) return EOF;
	do {
		ret = ret*10 + ch - '0';
	} while ((ch=getchar()) != ' ' && ch != '\n') ;
	return ret;
}
int cnt[DMAX+10];
int main() {
	int i,j,k,ans;
	while ((n=get_val()) != EOF) {
		l = get_val();
		for (i=0;i<n;i++) {
			app[i].p = get_val();
			app[i].d = get_val();
		}
		sort(app,app+n);
		ans = 0;
		for (i=0;i<=DMAX;i++) cnt[i] = l;
		for (i=0;i<n;i++) {
			for (j=app[i].d;j>=0;j--) {
				if (cnt[j] > 0) {
					cnt[j] --;
					ans += app[i].p;
					break;
				}
			}
		}
		printf("%d\n",ans);
	}
}