3065363_ac_203ms_280k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <algorithm>

using namespace std;

int n;
struct Node
{
	int b, p;
};

struct node 
{
	int num;
	Node fac[101];
}dev[101];

int allb[10001];
int nb;

bool cmp(Node a,Node b)
{
	return a.p < b.p;
}

int main()
{
	int t, flag, mark;
	int i, j, k;
	double tmp, ans;

	scanf("%d",&t);
	while (t--)
	{
		scanf("%d",&n);
		nb = 0;
		for (i = 0; i < n; i++)
		{
			scanf("%d",&dev[i].num);
			for (j = 0; j < dev[i].num; j++)
			{
				scanf("%d%d",&dev[i].fac[j].b,&dev[i].fac[j].p);
				allb[nb++] = dev[i].fac[j].b;
			}
			sort(dev[i].fac,dev[i].fac+dev[i].num,cmp);
		}
		ans = 0;
		for (i = 0; i < nb; i++)
		{
			flag = 0;
			tmp = 0;
			for (j = 0; j < n; j++)
			{
				mark = 1;
				for (k = 0; k < dev[j].num; k++)
				{
					if (dev[j].fac[k].b >= allb[i])
					{
						mark = 0;
						tmp += dev[j].fac[k].p;
						break;
					}
				}
				if (mark)
				{
					flag = 1;
					break;
				}
			}
			if (flag)
			{
				continue;
			}
			tmp = allb[i]*1.0/tmp;
			if(tmp > ans)
				ans = tmp;
		}
		printf("%.3lf\n",ans);
	}
	return 0;
}