3.txt

poj1018的源代码

Source

Problem Id:1018  User Id:00204726 
Memory:112K  Time:40MS 
Language:C++  Result:Accepted

Source 
#include <iostream.h> 
#include <stdlib.h> 
#include <stdio.h> 
#include <string.h> 

struct manu 
{ 
    int b,p; 
}; 

struct device 
{ 
    struct manu m[100]; 
    int n; 
}device[100]; 

struct 
{ 
    int bw[10000]; 
    int n; 
}bw; 
int n; 
int cmp(const void* a,const void* b) 
{ 
    if (((struct manu *)a)->b>((struct manu*)b)->b) 
        return 1; 
    else 
        if (((struct manu *)a)->b<((struct manu *)b)->b) 
            return(-1); 
        else 
            return(0); 
} 

void main() 
{ 
    int i,j,k,p,cases,mcases; 
    scanf("%d",&cases); 
    for (mcases=1;mcases<=cases;mcases++) 
    { 
        scanf("%d",&n); 
        for (i=0;i<n;i++) 
        { 
            scanf("%d",&device[i].n); 
            for (j=0;j<device[i].n;j++) 
                scanf("%d%d",&device[i].m[j].b,&device[i].m[j].p); 
            for (j=0;j<device[i].n;j++) 
            { 
                for (k=j+1;k<device[i].n;k++) 
                { 
                    if (device[i].m[k].b<=device[i].m[j].b&&device[i].m[k].p>=device[i].m[j].p) 
                    { 
                        device[i].m[k]=device[i].m[device[i].n-1]; 
                        k--;device[i].n--; 
                    } 
                    else 
                    { 
                        if (device[i].m[k].b>=device[i].m[j].b&&device[i].m[k].p<=device[i].m[j].p) 
                        { 
                            device[i].m[j]=device[i].m[device[i].n-1]; 
                            j--;device[i].n--; 
                            break; 
                        } 
                    } 
                } 
            } 
            qsort(device[i].m,device[i].n,sizeof(struct manu),cmp); 
            if (i==0) 
            { 
                for (j=0;j<device[0].n;j++) 
                    bw.bw[j]=device[0].m[j].b; 
                bw.n=device[0].n; 
            } 
            else 
            { 
                for (j=k=0;j<device[i].n;j++) 
                { 
                    for (;bw.bw[k]<device[i].m[j].b&&k<bw.n;k++); 
                    if (k!=bw.n) 
                    { 
                        if (bw.bw[k]>device[i].m[j].b) 
                        { 
                            for (p=bw.n;p>k;p--) 
                                bw.bw[p]=bw.bw[p-1]; 
                            bw.bw[k]=device[i].m[j].b; 
                            bw.n++; 
                        } 
                    } 
                } 
                bw.n=k+1; 
            } 
        } 
        float mbp,bp; 
        for (i=0,mbp=0;i<bw.n;i++) 
        { 
            float price=0; 
            for (j=0;j<n;j++) 
            { 
                for (k=0;k<device[j].n&&device[j].m[k].b<bw.bw[i];k++); 
                price=price+device[j].m[k].p; 
            } 
            bp=bw.bw[i]/price; 
            if (bp>mbp) mbp=bp; 
        } 
        printf("%0.3f\n",mbp); 
    } 
}