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;
}