首页 > 代码库 > bzoj1029题解
bzoj1029题解
【解题思路】
贪心,先按结束时间排序,从左到右扫描过去,如果当前建筑可以修复则入大根堆,否则,若其修复时间比堆顶小则弹出堆顶并入堆,处理完堆后则更新总时间。复杂度O(nlog2n)。
【参考代码】
1 #pragma GCC optimize(2) 2 #include <algorithm> 3 #include <cstdio> 4 #include <functional> 5 #include <set> 6 #define REP(i,low,high) for(register int i=(low);i<=(high);i++) 7 using namespace std; 8 struct node 9 {10 int ft,et;11 node() {}12 int input() {return scanf("%d%d",&ft,&et);}13 bool operator<(const node &another)const{return et<another.et;}14 }a[150010];15 int n;16 multiset<int, greater<int> > sav;17 int main()18 {19 scanf("%d",&n),sav.clear(); REP(i,1,n) a[i].input(); sort(a+1,a+n+1);20 int ans=0,now=0;21 REP(i,1,n)22 {23 if(a[i].ft+now<=a[i].et) sav.insert(a[i].ft),ans++,now+=a[i].ft;24 else25 {26 multiset<int>::iterator tp=sav.begin();27 if(*tp>a[i].ft) now+=a[i].ft-*tp,sav.erase(tp),sav.insert(a[i].ft);28 }29 }30 return printf("%d\n",ans),0;31 }
bzoj1029题解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。