A40 反悔贪心 P2949 [USACO] Work Scheduling G

方法：按结束时间从小到大排序，小根堆维护工作的报酬。对于工作i，如果 q.size() < a[i].t 表示有时间可以选这个工作，否则，需要将堆里的最小的拿出来换成当前这个工作，前提是报酬大于堆顶（堆里的最小值）。由于t从小到大排序，堆内元素数量只可能比当前截止时间多1。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 10;

struct node
{
	int t, w;
} a[N];
bool cmp(node n1, node n2) { 
	return (n1.t != n2.t) ? n1.t < n2.t : n1.w > n2.w; 
}

priority_queue<int, vector<int>, greater<int>> q;

int main()
{
	int n;scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%d%d", &a[i].t, &a[i].w);

	sort(a + 1, a + n + 1, cmp);
	long long ans = 0;
	for (int i = 1; i <= n; i++)
	{
		if (q.size() < a[i].t)
		{
			ans += a[i].w;
			q.push(a[i].w);
		}
		else
		{
			if (q.top() < a[i].w)
			{
				ans -= q.top();
				q.pop();
				ans += a[i].w;
				q.push(a[i].w);
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}