https://cn.vjudge.net/problem/UVA-1153

题目

有 $n$ （$n\leqslant800000$）个工作，已知每个工作需要的时间 $q_i$ 和截止时间 $d_i$（必须在此之前完成），最多能完成多少工作？工作只能串行完成。第一项任务开始的时间不早于时刻0。

题解

考虑这样的图……

考虑不出来

放弃= =

题目提示按截止时间从小到大排序

因为是串行的，所以只用考虑接下来选择哪一个……

能选择的尽量选，不能选择的想办法和前面用时更长的替换，并且解不会变差。（知道答案编过程……不过好在知道这种贪心策略了）

AC代码

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") #include<bits/stdc++.h> using namespace std; #define REP(r,x,y) for(register int r=(x); r<(y); r++) #define REPE(r,x,y) for(register int r=(x); r<=(y); r++) #ifdef sahdsg #define DBG(...) printf(__VA_ARGS__) #else #define DBG(...) #endif #define MAXN 800007 int n; struct node{ int q,d; } arr[MAXN]; bool operator<(const node&l, const node&r) { return l.d<r.d || (l.d==r.d && l.q<r.q); } priority_queue<int,vector<int>,less<int> > pq; int main() { int t; scanf("%d", &t); bool fi=false; while(0<t--) { if(fi) putchar('\n'); else fi=true; scanf("%d", &n); REP(i,0,n) { scanf("%d%d", &arr[i].q, &arr[i].d); } sort(arr,arr+n); int now=0; int ans=0; while(!pq.empty()) pq.pop(); REP(i,0,n) { if(now+arr[i].q<=arr[i].d) { now += arr[i].q; pq.push(arr[i].q); ans++; } else { pq.push(arr[i].q); int k=pq.top(); pq.pop(); now -= k; now += arr[i].q; } } printf("%d\n", ans); } return 0; }

 

转载于:https://www.cnblogs.com/sahdsg/p/10520459.html