2296.cpp

来自「哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码」· C++ 代码 · 共 46 行

/*  This Code is Submitted by wywcgs for Problem 2296 on 2006-07-25 at 19:24:15 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long int64;
const int N = 1024;
 
class Person {
public:
	int f, b;
	void make() { scanf("%d %d", &f, &b); }
	int tran(int64, int) const;
};
int Person::tran(int64 t, int F) const {
	if(b) t -= 2*F-f;
	else t -= f;
	int k = t / (2*F); t %= (2*F);
	if(t >= F) k++;
	return k;
}
 
int main()
{
	int n, f, b;
	int t, T, i;
	Person p[N];
	
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d %d %d", &n, &f, &b);
		for(i = 0; i < n; i++) p[i].make();
		int64 l = 0, h = 2*b*f;
		while(l != h) {
			int64 mid = (l+h)/2; 
			int tk = 0;
			for(i = 0; i < n; i++) tk += p[i].tran(mid, f);
			if(tk >= b) h = mid;
			else l = mid+1;
		}
		printf("%lld\n", h);
	}
	
	return 0;
}