HDUOJ 1789 Doing Homework again（贪心）

solution：难点在于找到贪心策略，我们发现按时间排序并不能满足要求，于是改用分数排序

#include <bits/stdc++.h>
using namespace std;

struct node {
	int date;
	int score;
}a[1001];

//标记第i天是否可用
int book[1001];

bool cmp(node a, node b)
{
	if (a.score != b.score)return a.score > b.score;
	return a.date < b.date;
}

int main()
{
	int t, n;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d", &n);
		for (int i = 0; i < n; ++i)scanf("%d", &a[i].date);
		for (int i = 0; i < n; ++i)scanf("%d", &a[i].score);
		sort(a, a + n, cmp);
		fill(book, book + 1001, 0);
		int res = 0;
		for (int i = 0; i < n; ++i)
		{
			int j;
			for (j = a[i].date; j > 0; --j)
			{
				if (!book[j]){
					book[j] = 1;
					break;
				}
			}
			if (j <= 0)res += a[i].score;
		}
		cout << res << endl;
	}
	return 0;
}