Problem 10026 Shoemaker's Problem，工作排序

本來我打算放棄解這題，不過 google 了一下，發現只須要用到排序，就能解決這一題。

假設有兩個工作要比較，d1, m1 和 d2, m2 (d 為工作天，m 為延遲罰金)，要比較它們的大小就讓它們工作天以及延遲罰金互乘，再去比較大小，則可很輕易的就排序出結果，例如： 3個工作天，延遲罰金 5 以及 4 個工作天，延遲罰金 7，而 3 * 7 > 4 * 5，則後者排序在前，前者排序在後。

關鍵程式碼如下：

#define SIZE 1001
struct Job
{
    int num;
    int wDay;
    int dMoney;
};
struct Job job[SIZE], r;

主程式內 ...

scanf("%d", &m);
for (i = 0; i < m; i ++)
{
    scanf("%d %d", &day ,&money);
    job[i].wDay = day, job[i].dMoney = money;
    job[i].num = i + 1;
    for (j = i; j >= 1; j --)
    {
        if (job[j].wDay * job[j - 1].dMoney < 
            job[j - 1].wDay * job[j].dMoney)
        {
            r = job[j], job[j] = job[j - 1],
            job[j - 1] = r;
        }
        else break;
    }
}

最後只要逐個印出 job 陣列內的 num 值就好了。

By David.K

p10026題目連結
回ACM題庫目錄
回首頁