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

虽然思绪一片混乱,但居然一次AC,奇迹啊

Posted by 200730690105 at 2009-03-23 18:05:35 on Problem 1018
唉,为什么那次没有这种运气

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