2005.cpp

来自「这是哈尔滨工业大学acmOJ的源代码」· C++ 代码 · 共 49 行

/*  This Code is Submitted by wywcgs for Problem 2005 on 2006-05-26 at 12:31:15 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int JN = 1024;
const double eps = 1e-4;

class Job {
public:
	int s, r;
	double end;
	void make() { scanf("%d %d", &s, &r); }
	bool operator <(const Job& j) const { return end < j.end; }
	void lmt(const double rr) { end = rr*r+s; }
};

int main()
{
	Job job[JN];
	int n, i;
	
	while(scanf("%d", &n) != EOF && n != 0) {
		int tr = 0;
		for(i = 0; i < n; i++) { job[i].make(); tr += job[i].r; }
		double l, h;
		for(i = 0; i < n; i++) {
			double jl = (tr-job[i].s)*1.0/job[i].r;
			if(i == 0) l = h = jl;
			else { l = min(l, jl); h = max(h, jl); }
		}
		while(h - l > eps) {
			double mid = (h + l) / 2;
			for(i = 0; i < n; i++) job[i].lmt(mid);
			sort(job, job+n);
			int sum = 0;
			for(i = 0; i < n; i++) {
				sum += job[i].r;
				if(sum > job[i].end) break;
			}
			if(i == n) h = mid;
			else l = mid;
		}
		printf("%.3lf\n", (h+l)/2);
	}
	
	return 0;
}