首页 > 代码库 > AC日记——[JSOI2007]建筑抢修 bzoj 1029
AC日记——[JSOI2007]建筑抢修 bzoj 1029
1029
思路:
贪心,而且,stl水过;
然而神特么输出que.size()就错!
代码:
#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define maxn 150005#define ll long longstruct BuildingType { ll lit,time;};struct BuildingType ai[maxn];ll n,sum,ans;inline void in(ll &now){ char Cget=getchar();now=0; while(Cget>‘9‘||Cget<‘0‘) Cget=getchar(); while(Cget>=‘0‘&&Cget<=‘9‘) { now=now*10+Cget-‘0‘; Cget=getchar(); }}bool cmp(BuildingType aa,BuildingType bb){ if(aa.lit==bb.lit) return aa.time<bb.time; else return aa.lit<bb.lit;}priority_queue<ll>que;int main(){ in(n); for(ll i=1;i<=n;i++) in(ai[i].time),in(ai[i].lit); sort(ai+1,ai+n+1,cmp); for(ll i=1;i<=n;i++) { if(sum+ai[i].time<=ai[i].lit) que.push(ai[i].time),sum+=ai[i].time,ans++; else { if(que.empty()) continue; if(ai[i].time<que.top()) sum-=que.top(),que.pop(),que.push(ai[i].time),sum+=ai[i].time; } } printf("%lld\n",ans); return 0;}
AC日记——[JSOI2007]建筑抢修 bzoj 1029
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。