AOJ 2180 Water Tank
Water Tank
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2180
問題概要
重なり合うことのない、水槽からs秒目からt秒目までuリットル水を排出するスケジュールがある。
1日は86,400秒ある。
連日このスケジュールを繰り返しても水がなくならないように、
毎秒注がなければならない水の量を最小化せよ。
水の量初期値Lリットルであり、Lリットルを超えて注いでも溢れる。
解法
二分探索。
86400 * lg(10^12)くらい。
300万オーダー。
2回連続で試して終了時の水量が減少傾向でなければおk
ソース
#include<iostream> #include<vector> #include<cstdlib> #include<cmath> #include<cstdio> #define REP(i, b, n) for(int i = b; i<(int)n; i++) #define rep(i, n) REP(i, 0, n) using namespace std; class Out{ public: int s, t, v; bool toNext(int now){ if(now >= t)return true; return false; } int val(int now){ if(now >= s && now < t)return v; return 0; } }; bool isOk(double IN, vector<Out> &O, double L, double capa){ const int T = 86400; int which = 0; rep(i, T){ if(which < (int)O.size() && O[which].toNext(i)){ which++; } if(which < (int)O.size())L += (IN - O[which].val(i)); else L += IN; if(L <= 0)return false; if(L > capa)L=capa; } double pre = L; which = 0; rep(i, T){ if(which < (int)O.size() && O[which].toNext(i)){ which++; } if(which < (int)O.size())L += (IN - O[which].val(i)); else L += IN; if(L <= 0)return false; if(L > capa)L=capa; } return (abs(pre - L) < 0.0000000001); } int main(){ int n, l; while(cin >> n >> l){ if(n == 0 && l == 0)break; vector<Out> O(n); rep(i, n){ cin >> O[i].s >> O[i].t >> O[i].v; } double left = 0, right = 1e7; while(1){ if(abs(left - right) < 0.00000001)break; double mid = (left + right) / 2.0; if(isOk(mid, O, l, l)){ right = mid; } else left = mid; } printf("%.7f\n", left); } return 0; }