1570.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1570 on 2006-07-07 at 11:47:20 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int TN = 128;

class Task {
public:
	int e, p, en;
	void make() { scanf("%d %d", &e, &p); en = 0; }
	bool operator <(const Task& t) const { return p < t.p; }
	bool exeable(int) const;
};
bool Task::exeable(int ct) const {
	int k = ct/p;
	return (en >= k*e && en < (k+1)*e);
}

int main()
{
	int t, T, i, j, n;
	Task task[TN];

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d", &n);
		for(i = 0; i < n; i++) task[i].make();
		sort(task, task+n);
		int last = -1;
		for(i = 0; i < task[n-1].p; i++) {
			for(j = 0; j < n; j++)
				if(task[j].exeable(i)) { task[j].en++; break; }
			if(!task[n-1].exeable(i) && last == -1) last = i;
		}
		bool can = true;
		for(i = 0; i < n; i++)
			if(!task[i].exeable(task[n-1].p)) can = false;
		printf("%d\n", can ? last+1 : -1);
	}
	
	return 0;
}