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 |
虽然思绪一片混乱,但居然一次AC,奇迹啊唉,为什么那次没有这种运气 #include <stdio.h> #include <string.h> int n; int m[105]; int max[105]; int min; double ans,dp[100005],s; int minp[105],sb[105],minb; typedef struct { int b[105],p[105]; }node; node a[105]; int main() { int t; int i,j,k; scanf("%d",&t); while(t--) { scanf("%d",&n); min=~(1<<31); for(i=1;i<=n;i++) { scanf("%d",&m[i]); max[i]=0; for(j=1;j<=m[i];j++) { scanf("%d %d",&a[i].b[j],&a[i].p[j]); if(max[i]<a[i].b[j]) max[i]=a[i].b[j]; } if(min>max[i]) min=max[i]; } memset(dp,0,sizeof(dp)); for(i=1;i<=min;i++) { if(!dp[i]) { minb=~(1<<31); s=0; for (j=1;j<=n;j++) { minp[j]=~(1<<31); sb[j]=~(1<<31); for(k=1;k<=m[j];k++) { if(a[j].b[k]>=i && minp[j]>a[j].p[k]) {minp[j]=a[j].p[k];sb[j]=a[j].b[k];} } s=s+minp[j]; if(minb>sb[j]) minb=sb[j]; } } dp[minb]=(double)minb/s; } ans=0; for(i=1;i<=min;i++) { if(ans<dp[i]) ans=dp[i]; } printf("%.3lf\n",ans); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator