2.txt

poj1018的源代码

Source

Problem Id:1018  User Id:Epic 
Memory:108K  Time:40MS 
Language:C++  Result:Accepted

Source 
#include <iostream.h> 
#include <stdlib.h> 
#include <search.h> 
#include <limits.h> 
#include <stdio.h> 
typedef int devicetype[2]; // 0-bandwidth, 1-price 
int compare(const void* a, const void* b){ 
    if ( ((int*)a)[0]<((int*)b)[0] ) return 1; 
    if ( ((int*)a)[0]>((int*)b)[0] ) return -1; 
    return 0; 
} 
int main() { 
    int t,n; 
    int m[100]; 
    int p[100]; // front pointer 
    int q[100]; // best pointer 
    devicetype val[100][100]; 
    cin>>t; 
    for ( int i=0; i<t; i++) { 
        cin>>n; 
        for ( int j=0; j<n; j++){ 
            cin>>m[j]; 
            for ( int k=0; k<m[j]; k++) 
                cin>>val[j][k][0]>>val[j][k][1]; 
            qsort(val[j],m[j],sizeof(devicetype),compare); 
        } 
        float max; 
        int bb,pp; // minimum bandwidth and total price 
        bb = INT_MAX; 
        pp = 0; 
        for ( j=0; j<n; j++) { 
            p[j] = 0; 
            q[j] = 0; 
            if ( val[j][0][0]<bb ) bb = val[j][0][0]; 
            pp += val[j][0][1]; 
        } 
        max = float(bb)/pp; 
        bool flag = true; 
        while ( flag ) { 
            flag = false; 
            int index = -1; 
            int tempbb = -1; 
            for ( j=0; j<n; j++) { 
                if ( p[j] == m[j]-1 ) continue; 
                if ( val[j][p[j]+1][0]>tempbb ) { 
                    index = j; 
                    tempbb = val[j][p[j]+1][0]; 
                    flag = true; 
                } 
            } 
            if ( !flag ) continue; 
            p[index]++; 
            if ( val[index][p[index]][1]<val[index][q[index]][1] ) { 
                if ( val[index][p[index]][0]<bb ) bb = val[index][p[index]][0]; 
                pp -= val[index][q[index]][1]; 
                q[index] = p[index]; 
                pp += val[index][q[index]][1]; 
                if ( float(bb)/pp > max ) max = float(bb)/pp; 
            } 
        } 
        printf("%.3f\n",max); 
    } 
    return 0; 
}