[luoguP2949] [USACO09OPEN]工作调度Work Scheduling（贪心 + 优先队列）
这个题类似于建筑抢修。
先按照时间排序。
如果当前时间小于任务截止时间就选，
否则，看看当前任务价值是否比已选的任务的最小价值大，
如果是，就替换。
可以用优先队列。
——代码
1 #include <queue> 2 #include <cstdio> 3 #include <iostream> 4 #include <algorithm> 5 #define LL long long 6 7 const int MAXN = 1e6 + 5; 8 int n; 9 LL tim, ans; 10 struct node 11 { 12 LL x, y; 13 }p[MAXN]; 14 std::priority_queue <LL, std::vector <LL>, std::greater <LL> > q; 15 16 inline LL read() 17 { 18 LL x = 0, f = 1; 19 char ch = getchar(); 20 for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1; 21 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0'; 22 return x * f; 23 } 24 25 inline bool cmp(node x, node y) 26 { 27 return x.x < y.x; 28 } 29 30 int main() 31 { 32 int i; 33 n = read(); 34 for(i = 1; i <= n; i++) p[i].x = read(), p[i].y = read(); 35 std::sort(p + 1, p + n + 1, cmp); 36 for(i = 1; i <= n; i++) 37 { 38 if(tim < p[i].x) tim++, ans += p[i].y, q.push(p[i].y); 39 else if(tim == p[i].x && p[i].y > q.top()) 40 { 41 ans += p[i].y - q.top(); 42 q.pop(); 43 q.push(p[i].y); 44 } 45 } 46 printf("%lld ", ans); 47 return 0; 48 }