uvalive 2757(贪心)

题意：有n个任务，给出了每个任务的奖金和期限，每个任务完成都要1个时间单位，问选择一些任务都按时完成可以得到的最多奖金是多少。

题解：先按时间排序，倒着枚举所有时间点，给它分配奖金最大的且未被分配的任务。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 10005;
struct P {
	int pi, d, flag;
}p[N];
int n, res;

bool cmp(P a, P b) {
	if (a.d != b.d)
		return a.d < b.d;
	return a.pi > b.pi;
}

void solve(int dt) {
	for (int i = dt; i >= 1; i--) {
		int maxx = -1, index;
		for (int j = n - 1; j >= 0, p[j].d >= i; j--) {
			if (!p[j].flag && maxx < p[j].pi) {
				maxx = p[j].pi;
				index = j;
			}
		}
		if (maxx != -1) {
			p[index].flag = 1;
			res += maxx;	
		}
	}
}

int main() {
	while (scanf("%d", &n) == 1) {
		for (int i = 0; i < n; i++)
			p[i].flag = 0;
		for (int i = 0; i < n; i++)
			scanf("%d%d", &p[i].pi, &p[i].d);
		sort(p, p + n, cmp);
		int dt = p[n - 1].d;
		res = 0;
		solve(dt);
		printf("%d\n", res);
	}
}

uvalive 2757(贪心)

原文：http://blog.csdn.net/hyczms/article/details/44598875