| ||||||||||
| 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