此题如果bandwidth也很大，就没法DP了。
但是三分法表示无压力，考虑到最后的结果肯定是关于bandwidth的一个单峰函数，将所有的bandwidth统计出来，排序之后对着他们三分就可以了。

代码写的丑，凑活一下 :P

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int n;
int t;
int len[111];
int b[111][111];
int p[111][111];
int a[222222];
int m;

double calc(int x)
{
	double sum(0);
	for (int i=1; i<=n; i++)
	{
		int xiao = 2147483647;
		for (int j=1; j<=len[i]; j++)
			if (b[i][j] >= x) xiao = min(xiao, p[i][j]);
		sum += xiao;
	}
	return x / sum;
}
int main(void)
{
	int i,j,k,ci,cici,cicici;

	for (scanf("%d", &t); t; t--)
	{
		scanf("%d", &n);
		for (i=1; i<=n; i++)
		{
			scanf("%d", &len[i]);
			for (j=1; j<=len[i]; j++)
			{
				scanf("%d%d", &b[i][j], &p[i][j]);
				a[++m] = b[i][j];
			}			
		}

		sort(a+1, a+1+m);

		int left = 1, right = m, mid1, mid2;
		double f1, f2;
		while(left + 1 < right)
		{
			mid1 = (left + right) / 2;
			mid2 = (mid1 + right) / 2;
			f1 = calc(a[mid1]);
			f2 = calc(a[mid2]);
			if (f1 < f2) left = mid1;
			else right = mid2;
		}
		printf("%.3lf\n", max(calc(a[left]), calc(a[right])));
	}
	return 0;
}

• Re:三分法 飘过 (14) weihaohaoren 2011-10-02 18:56:36
• Re:三分法 飘过 (61) lovepal4 2012-03-03 04:49:35
  • Re:三分法 飘过 (71) hjwdzh 2012-03-08 16:42:46
    • Re:三分法 飘过 (48) hjwdzh 2012-03-08 16:43:16