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