1604.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1604 on 2005-12-09 at 22:10:15 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 10240;

int main()
{
	int cable[MAX];
	int n, k, i;
	int begin, end;
	
#ifndef  ONLINE_JUDGE
	freopen("E:\\1\\cable.in", "r", stdin);
	freopen("E:\\1\\cablew.out", "w", stdout);
#endif
	while(scanf("%d %d", &n, &k) != EOF && n != 0 && k != 0) {
		for(i = 0; i < n; i++) {
			int a, b;
			scanf("%d.%d", &a, &b);
			cable[i] = a * 100 + b;
		}
		sort(cable, cable+n);
		begin = 0;
		end = cable[n-1];
		while(end != begin) {
			int mid = (begin + end + 1) / 2;
			int X = lower_bound(cable, cable+n, mid) - cable;
			int cut = 0;
			for(i = X; i < n; i++) {
				cut += cable[i] / mid;
			}
			if(cut >= k) {
				begin = mid;
			} else {
				end = mid - 1;
			}
		}
		printf("%d.%02d\n", begin/100, begin%100);
	}
	
	return 0;
}