傳送門:BZOJ1029

還記得線段覆蓋嗎？

我們將建筑物按Deadline排序，然后掃描排序后數(shù)組，假設(shè)當(dāng)前建筑物能夠被修建。則修建，否則。假設(shè)當(dāng)前建筑物所用時(shí)間小于修過的建筑物最大時(shí)間。則放棄最大時(shí)間，改修它。
這個(gè)算法的正確性是顯然的。

代碼上的小細(xì)節(jié)見下：

#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <algorithm> #include <iostream> #include <queue> using namespace std;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; }

轉(zhuǎn)載于:https://www.cnblogs.com/zsychanpin/p/7076513.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ1029的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。