Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

过了,不过效率不高啊,有更好的算法吗??

Posted by church at 2007-05-19 10:46:43 on Problem 1018
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator