传送门:BZOJ1029
还记得线段覆盖吗？
我们将建筑物按Deadline排序，然后扫描排序后数组，如果当前建筑物可以被修建，则修建，否则，如果当前建筑物所用时间小于修过的建筑物最大时间，则放弃最大时间，改修它。 这个算法的正确性是显然的。 代码上的小细节见下：
;struct Node{int Needtime;int Deadline;bool operator <(const Node& a)const{return Deadline<a.Deadline;}};Node da[150005];int n;priority_queue<int> Q;void Readdata(){freopen(“loli.in”,”r”,stdin);scanf(“%d”,&n);for(int i=1;i<=n;i++)scanf(“%d%d”,&da[i].Needtime,&da[i].Deadline);}void Solve(){sort(da+1,da+1+n);int used=0;Q.push(0);for(int i=1;i<=n;i++)if(used+da[i].Needtime<=da[i].Deadline){Q.push(da[i].Needtime);used+=da[i].Needtime;}elseif(da[i].Needtime<Q.top()){used+=(da[i].Needtime-Q.top());Q.pop();Q.push(da[i].Needtime);}printf(“%d”,Q.size()-1);}void Close(){fclose(stdin);fclose(stdout);}int main(){Readdata();Solve();Close();return 0;}
，都属于昨天。哪怕那山再青，那水再秀，
