ACM UVA 10026 (Shoemaker's Problem)

题目:

解题思路:

设有N个job，j1, j2, j3, ... jn。

在第K+1天我们要选择一个job时，我们能否greedily找到一个最优的job呢？答案是肯定
的。
我们就任意选出两个job(jm和jn)来进行比较。我们将jm和jn作为两个连续的job来比较，
这样可以确保之后的job排列不依赖于jm和jn的排列。

jm排在jn前面：
costm = ... + S(jm)*K + S(jn)*(K+T(jm)) + ...
jn排在jm前面：
costn = ... + S(jn)*K + S(jm)*(K+T(jm)) + ...

因此，我们只需要计算不等式 costm <= costn 。
最终可以推导出 S(jm)/T(jm) <= S(jn)/T(jn)

代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int day;
    int pay;
    int index;
} job;

int compare(const void *v1, const void *v2);

int main()
{
    int case_num = 0;
    job jobs[1000];
    int job_num = 0;
    int i = 0;

    scanf("%d", &case_num);
    for (; case_num != 0; case_num--) {
        scanf("%d", &job_num);
        for (i = 0; i < job_num; i++) {
            scanf("%d %d", &(jobs[i].day), &(jobs[i].pay));
            jobs[i].index = i+1;
        }

        qsort(jobs, job_num, sizeof(job), compare);
        for (i = 0; i < job_num; i++) {
            printf("%d", jobs[i].index);
            if (i+1 == job_num) {
                printf("\n");
            } else {
                printf(" ");
            }
        }
        if (case_num > 1) {
            printf("\n");
        }
    }
}

int compare(const void *v1, const void *v2)
{
    job *job1 = (job*)v1;
    job *job2 = (job*)v2;
    double rate1 = (double)(job1->pay)/(double)(job1->day);
    double rate2 = (double)(job2->pay)/(double)(job2->day);

    if (rate1 < rate2) {
        return 1;
    } else if (rate1 > rate2) {
        return -1;
    } else {
        return job1->index - job2->index;
    }
}