POJ2970 The lazy programmer
解いてる人が233人で難しそうとか思ったけど考えてみると普通にgreedyに選んでいけばいいだけということに気付く。
なんでこんなに通してる人少ないんだろう。
#include<stdio.h> #include<vector> #include<algorithm> #include<set> #include<queue> using namespace std; #define mt(A,B,C) make_pair(A,make_pair(B,C)) typedef pair<int,int>pii; typedef pair<int,pii>pi3; typedef pair<int,double>pid; int main() { int num; scanf("%d",&num); vector<pi3>vec; for(int i=0;i<num;i++) { int za,zb,zc; scanf("%d%d%d",&za,&zb,&zc); vec.push_back(mt(zc,za,zb)); } sort(vec.begin(),vec.end()); priority_queue<pii>que; double ret=0; int tim=0; for(int i=0;i<num;i++) { tim+=vec[i].second.second; que.push(make_pair(vec[i].second.first,vec[i].second.second)); if(tim>vec[i].first) { for(;;) { pii zan=que.top(); que.pop(); if(tim-zan.second<=vec[i].first) { zan.second-=tim-vec[i].first; ret+=double(tim-vec[i].first)/double(zan.first); tim=vec[i].first; que.push(zan); break; } else { ret+=double(zan.second)/double(zan.first); tim-=zan.second; } } } } printf("%.2lf\n",ret); }
なんとなくJOI過去問の「ダンジョン」に似てる気がした。