| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
过了,不过效率不高啊,有更好的算法吗??#include <stdio.h>
int a[105][105],p[105][105],min[105];
int b[105],last[105],n;
float max;
void work(int u);
void sort(int h,int l ,int step)
{
int i,j,mid,k;
i=h; j=l;
mid=a[step][(i+j)/2];
do
{
while ((a[step][i]<mid)&& (i<l)) i++;
while ((a[step][j]>mid)&& (j>h)) j--;
if (i<=j)
{
k=a[step][i]; a[step][i]=a[step][j]; a[step][j]=k;
k=p[step][i]; p[step][i]=p[step][j]; p[step][j]=k;
i++; j--;
}
}while (i<=j);
if (i<l) sort(i,l,step);
if (j>h) sort(h,j,step);
}
void main()
{
int c,i,k,j;
scanf("%d",&c);
for(i=0;i<c;i++)
{
max=0;
scanf("%d",&n);
for(j=1;j<=n;j++)
{
scanf("%d",&b[j]);
for(k=1;k<=b[j];k++)
scanf("%d %d",&a[j][k],&p[j][k]);
sort(1,b[j],j);
}
for(j=1;j<=n;j++)
work(j);
printf("%0.3f\n",max);
}
}
void work(int u)
{
int i,j,k;
long sum;
float m;
for(i=1;i<=n;i++)
{
last[i]=b[i];
min[i]=30000;
}
for(i=b[u];i>0;i--)
{
sum=p[u][i];
for(j=1;j<=n;j++)
if (j!=u)
{
for(k=last[j];k>0;k--)
{
if (a[u][i]>a[j][k])
break;
if (p[j][k]<min[j])
min[j]=p[j][k];
}
if (k==b[j])
break;
else
last[j]=k;
sum+=min[j];
}
if ((k==b[j]) && (j<=n))
continue;
m=(float)a[u][i]/sum;
if (m>max)
max=m;
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator