1725.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1725 on 2005-09-20 at 00:12:44 */ 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int cmp(const void *, const void *);

int main()
{
    int qnum[1001][2], K, n;
    int qindex[1001];
    int i, j, minq;
    long long min, total;
    char word[50];
    
    for(n = 0; ; n++) {
        scanf("%s", word);
        if(!strcmp(word, "#")) {
            break;
        } else {
            scanf("%d %d", &qnum[n][0], &qnum[n][1]);
        }    
    }
    qsort(qnum, n, sizeof(qnum[0]), cmp);
    scanf("%d", &K);
    for(i = 0; i < n; i++) {
        qindex[i] = 1;
    }    
    total = 0;
    for(i = 0; i < K; i++) {
        min = 50000000;
        for(j = 0; j < n; j++) {
            while(qnum[j][1] * qindex[j] < total) {
                qindex[j]++;
            }
            if(qnum[j][1] * qindex[j] < min) {
                min = qnum[j][1] * qindex[j];
                minq = j;
            }
        }
        total = min;
        printf("%d\n", qnum[minq][0]);
        qindex[minq]++;
    }
    scanf("%d", &n);
    
    return 0;
}

int cmp(const void *a, const void *b)
{
    if(*(int*)a < *(int*)b) {
        return -1;
    } else {
        return 1;
    }    
}