传送门
贪心。
感觉最近脑子不太好用，不知道是不是线段树树剖和网络流把脑子写傻了。
一开始瞎那啥乱贪心
//Twenty#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>#include<cmath>#include<cstring>#include<queue>#include<vector>#include<ctime>typedef long long LL;using namespace std;const int maxn=150000+299;struct node{ ???int t1,t2; ???friend bool operator <(const node &A,const node &B) { ???????return A.t2<B.t2||(A.t2==B.t2&&A.t1<B.t1); ???}}p[maxn];int ans,n;int main(){ ???scanf("%d",&n); ???for(int i=1;i<=n;i++) ????????scanf("%d%d",&p[i].t1,&p[i].t2); ???sort(p+1,p+n+1); ???int now=0; ???for(int i=1;i<=n;) { ???????int j=i+1,flag=0; ???????if(now+p[i].t1>p[i].t2) {i++; continue;} ???????while(j<=n&&now+p[i].t1+p[j].t1>p[j].t2) { ???????????if(p[j].t1<p[i].t1) { i=j; flag=1; break; } ???????????j++; ???????????} ???????if(flag) continue; ???????now+=p[i].t1; ???????ans++; ???????i=j; ???} ???printf("%d\n",ans); ???return 0;}WA了，×掉它的数据
16
7 13
8 17
8 8
9 8
4 3
5 19
10 16
10 8
3 13
2 8
7 11
7 15
6 19
1 5
9 1
1 12
正解
不知道为何sxy大佬用set当堆，习惯用优先队列。
//Twenty#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>#include<cmath>#include<cstring>#include<queue>#include<vector>#include<ctime>typedef long long LL;using namespace std;const int maxn=150000+299;struct node{ ???int t1,t2; ???friend bool operator <(const node &A,const node &B) { ???????return A.t1<B.t1; ???}}p[maxn];int ans,n;bool cmp(const node &a,const node &b) { ???return a.t2<b.t2;}priority_queue<node>que;int main(){ ???scanf("%d",&n); ???for(int i=1;i<=n;i++) ????????scanf("%d%d",&p[i].t1,&p[i].t2); ???sort(p+1,p+n+1,cmp); ???int now=0; ???for(int i=1;i<=n;i++) { ???????if(now+p[i].t1<=p[i].t2) { ???????????ans++; ???????????now+=p[i].t1; ???????????que.push(p[i]); ????????} ???????else { ???????????if(!que.empty()) { ???????????????node tp=que.top(); ???????????????if(tp.t1>p[i].t1&&now-tp.t1+p[i].t1<=p[i].t2) { ???????????????????que.pop(); ???????????????????now=now-tp.t1+p[i].t1; ???????????????????que.push(p[i]); ????????????????} ???????????} ???????} ???} ???printf("%d\n",ans); ???return 0;}BZOJ 1029 [JSOI2007]建筑抢修
原文地址：http://www.cnblogs.com/Achenchen/p/7612436.html