Source Code

Problem: 1018		User: nimohunter
Memory: 544K		Time: 94MS
Language: G++		Result: Accepted
Source Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int size = 105;
struct dev
{
	int width, price;
};

dev device[size][size];
int low_width[size*size], low_price[size][size], num[size];

bool cmp(dev a, dev b)
{
	if (a.width == b.width) return a.price < b.price;
	return a.width < b.width;
}

int main()
{
	//freopen("nimo.in", "r", stdin);
	int cas, n;
	scanf("%d", &cas);
	while (cas--)
	{
		scanf("%d", &n);
		int n_device = 0;
		for (int i = 0; i < n; i++)
		{
			scanf("%d", &num[i]);
			for (int j = 0; j < num[i]; j++)
			{
				scanf("%d%d", &device[i][j].width, &device[i][j].price);
				low_width[n_device++] = device[i][j].width;
			}
		}
		sort(low_width, low_width+n_device);

		//low_price[i][j] is the lowest price which width is larger than device[i][j].width
		for (int i = 0; i < n; i++)
		{
			sort(device[i], device[i]+num[i], cmp);
			low_price[i][num[i]-1] = device[i][num[i]-1].price;
			for (int j = num[i]-2; j >= 0; j--)
				low_price[i][j] = min(device[i][j].price, low_price[i][j+1]);
		}

		double ans = 0;
		for (int k = 0; k < n_device; k++)
		{
			// current choose width = low_width[k];
			int sum_price = 0;
			bool flag = 0;
			for (int i = 0; i < n; i++)
			{
				int j;
				for (j = 0; j < num[i]; j++)
					if (device[i][j].width >= low_width[k]) break;
				if (j == num[i]) 
				{
					//the largest width in this group cannot support current width
					flag = 1;
					break;
				}
				sum_price += low_price[i][j];
			}
			if (flag) break;
			double tmp_ans = (double)low_width[k]/(double)sum_price;
			if (tmp_ans > ans) ans = tmp_ans;
		}
		printf("%.3f\n", ans);
	}
	return 0;
}