TopCoder SRM 267 Div1 Hard HairCuts

問題

9:00amに開き5:00pmに閉まる床屋がある。
客の来る時間のリストが与えられる。

床屋は、客が来たときに誰もいなければ、その客の髪を切り、
誰かがいれば、先に来た客全員の髪を切り終えてからその客の髪を切る。

一人の客の散髪には最低5分の時間がかかる。

最後の客が散髪を終えた時間が与えられるとき、
最も長く散髪に時間のかかった客の、散髪の時間の最小値を求めよ。

制約条件

客の数≦50

方針

二分探索。

一人の客にかかる時間がmであるとすると、
最後の客を終えるのにかかる時間がlastExit以前かどうかがO(n)で判定できる。

5以上の時間について二分探索すればいい。

ソースコード

int parse(string s){
	int a,b; sscanf(s.c_str(),"%d:%d",&a,&b);
	if(a<9)a+=12;
	return a*60+b;
}
bool ok(vi &t,int last,double mid){
	double now=9*60;
	rep(i,t.size()){
		now=max(1.0*t[i],now)+mid;
	}
	return now<=last;
}
class HairCuts {
	public:
	double maxCut(vector <string> enter, string lastExit) 
	{
		int n=enter.size(), last=parse(lastExit);
		vi t;
		rep(i,n)t.pb(parse(enter[i]));
		sort(all(t));
		
		double lo=5.0,hi=last-t[n-1],mid;
		rep(it,100){
			mid=(lo+hi)/2;
			
			if(ok(t,last,mid))lo=mid;
			else hi=mid;
		}
		return !ok(t,last,5)?-1:lo;
	}
};