Uva 10026: Shoemaker's problem

tags: 貪心法

鞋匠有

$N$ 項工作要完成，他知道自己每項工作需要多少工作天能夠完成
以及每個工作延誤一天需要繳多少延遲的費用
此外，延遲天數計算是從當天算到該工作開始的那天(意味著第一件工作沒罰金)
對了！ 他每天只能做一件工作，不是多工的哦！

題目有給一項測試資料 以這個測資來說
如果工作順序為

$1,2,3,4$ 則罰金：

$$0\times 4+1000\times 3+4\times 2+6\times 5=3038$$ 反之，如果工作順序為

$2,1,3,4$ 則罰金：

$$0\times 1000+1\times 4+4\times 2+6\times 5=42$$ 這個問題的目標是幫助鞋匠找出能使罰金最少的工作順序

Source: 題目傳送門

---

Original

題目敘述

Shoemaker has

$N$ jobs (orders from customers) which he must make. Shoemaker can work on only one job in each day.

For each

$i-th$ job, it is known the integer

$T_i(1\le T_i\le 1000)$, the time in days it takes the shoemaker to finish the job.

For each day of delay before starting to work for the

$i-th$ job, shoemaker must pay a fine of

$S_i(1\le S_i\le 10000)$ cents.

Question

Your task is to help the shoemaker, writing a program to find the sequence of jobs with minimal total fine.

Input format

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of thme as described below.

This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

First line of input contains as integer

$N(1\le N\le 1000)$.
The next

$N$ lines each contain two numbers:

• time (needs)
• fine (fine / day)

Output format

For each test case, the output must follow the description below.

The outputs of two consecutive cases will be separated by a blank line.

Your program should print the sequence of jobs with minimal fine. Each job should be represented by its number in input.
All integers should be placed on only one output line and separated by one space.

If multiple solutions are possible, print the first lexicographically.

Sample Input

​​​​1
​​​​4
​​​​3 4
​​​​1 1000
​​​​2 2
​​​​5 5

Sample Output

​​​​2 1 3 4

---

概念

• 貪心
  • 思考一個排序方法
  • 要怎麼找基準值
  • 穩定的排序法可以確保按照字典序排序

---

主要思路

• 像是機會成本的概念，我選擇先做哪一個工作，此時其它工作就會累計罰金，所以要找一個方式衡量目前選擇的重要性

• 對於適當排序的狀況，兩個相鄰的工作

  $a,b$，若順序為
  $ab$ 或
  $ba$ ，會注意到除了
  $ab$ 以外，其餘工作的罰金並不會改變，也就是說關鍵在於選
  $ab$ , 選
  $ba$ 哪個損失比較小

• 假設如下：

  Time	Fine
  $a_d$	$a_f$
  $b_d$	$b_f$

  • $\boxed{\text{case 1: a->b}}{a}_d\times b_f$
  • $\boxed{\text{case 2: b->a}}{b}_d\times a_f$

  In the first case, the inequality should be correct:

  $$a_d\times b_f\le b_d\times a_f$$ 同除以
  $b_f\times a_f$:
  $$\frac{a_d}{a_f}\le \frac{b_d}{b_f}$$

• 同上述結果，會發現兩兩比較時，只需要將

  $\frac{a_d}{a_f}$ 數值由小到大排序即可

• 字典序的問題則只需要選擇穩定的排序法，確保相同值時不會更動順序即可

---

程式碼

#include <iostream>
#include <cstring>

using namespace std;

typedef struct S_job{
    double important;
    int32_t order;
}s_job;

//按照重要程度去排序
int32_t compare(const void *a, const void *b){
    if ((((s_job *)a)->important) > (((s_job *)b)->important)) return 1;
    return 0;
}

int main(){

    int32_t t = 0;
    cin >> t;

    //拿來吃blank line的
    string temp;

    for (int32_t i = 0 ; i < t ; i ++){
        if (i != 0) cout << endl;

        getline(cin, temp);

        int32_t num = 0;
        cin >> num;

        s_job arr[num];

        for (int32_t j = 0; j < num ; j++){
            int32_t day = 0 , pen = 0;
            cin >> day >> pen;

            arr[j].order = j+1;
            arr[j].important = (double)day / pen;

        }

        qsort(arr, num, sizeof(s_job), compare);

        //blank要處理一下，其餘輸出即可
        int32_t blank = 0 ;
        for (int32_t j = 0 ; j < num ; j++){
            if (blank) cout << " ";
            cout << arr[j].order;
            blank = 1;
        }
        cout << endl;

    }

    return 0;
}