uvalive 2757(貪心)

uvalive 2757(貪心)

題意：有n個任務，給出了每個任務的獎金和期限，每個任務完成都要1個時間單位，問選擇一些任務都按時完成可以得到的最多獎金是多少。

題解：先按時間排序，倒著枚舉所有時間點，給它分配獎金最大的且未被分配的任務。

#include 
#include 
#include 
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);
	}
}