4878435_ac_625ms_472k.cpp

部分PKU上的源码

#include<iostream>
using namespace std;
struct set
{
	int b,i,j;
}q[10005];
struct de
{
	int b,p;
};
int tmin,tmax;
de x[110][110];
int n,xl[110];
float best;
void find(int a)
{
	set temp=q[a];
	int i,j;
	int all=0;
	for(i=1;i<=n;i++)
	{
		if(i==temp.i)
		{
			all+=x[i][temp.j].p;
		}
		else
		{
			int minp=10000;
			for(j=1;j<=xl[i];j++)
			{
				if(x[i][j].b>=temp.b)
				{
					if(x[i][j].p<minp)minp=x[i][j].p;
				}
			}
			all+=minp;
		}
	}
	float re=(float)temp.b/(float)all;
	if(re>best) best=re;
}
int main()
{
	int test;
	cin>>test;
	for(int count=0;count<test;count++)
	{
	cin>>n;
	int i,j;
	tmin=-1;
	tmax=10000;
	for(i=1;i<=n;i++)
	{
		cin>>xl[i];
		int ttmin=10000,ttmax=-1;
		for(j=1;j<=xl[i];j++)
		{
			cin>>x[i][j].b>>x[i][j].p;
			if(x[i][j].b>ttmax)ttmax=x[i][j].b;
			if(x[i][j].b<ttmin)ttmin=x[i][j].b;
		}
		if(ttmin>tmin)tmin=ttmin;
		if(ttmax<tmax)tmax=ttmax;
	}
	int ql=0;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=xl[i];j++)
		{
			if(x[i][j].b<=tmax&&x[i][j].b>=tmin)
			{
				q[ql].b=x[i][j].b;
				q[ql].i=i;
				q[ql].j=j;
				ql++;
			}
		}
	}
	best=0.0;
	for(i=0;i<ql;i++)
	{
		find(i);
	}
	printf("%.3lf\n",best);
	}
	return 0;
}