# Uva 10026: Shoemaker's problem
###### tags: `貪心法`

> 鞋匠有 $N$ 項工作要完成，他知道自己每項工作需要多少工作天能夠完成\
> 以及每個工作延誤一天需要繳多少延遲的費用\
> 此外，延遲天數計算是從當天算到該工作開始的那天(意味著第一件工作沒罰金)\
> 對了！ 他每天只能做一件工作，不是多工的哦！<br><br>
> 題目有給一項測試資料
> 以這個測資來說\
> 如果工作順序為 $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:** [題目傳送門](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=967)

{%pdf https://vj.z180.cn/67c23d3e823e0df266b139a6166f9322?v=1595137800%}

---

## *Original*

### 題目敘述

> Shoemaker has $N$ jobs (orders from customers) which he must make.
> Shoemaker can work on only one job in each day. <br><br>
> For each $i-th$ job, it is known the integer $T_i (1 \leq T_i \leq 1000)$, the time in days it takes the shoemaker to finish the job. <br><br>
> For each day of delay before starting to work for the $i-th$ job, shoemaker must pay a fine of $S_i (1 \leq S_i \leq 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.<br><br>
> This line is followed by a blank line, and there is also a **blank line between two consecutive inputs**.<br><br>
> First line of input contains as integer $N (1 \leq N \leq 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.<br><br>
> The outputs of two consecutive cases will be separated by a blank line.<br><br>
> 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.<br><br>
> 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$|

* $\fbox{case 1: a->b} \; a_d \times b_f$
* $\fbox{case 2: b->a} \; b_d \times a_f$

In the first case, the inequality should be correct:
$$a_d \times b_f \leq b_d \times a_f$$
同除以 $b_f \times a_f$:
$$\frac{a_d}{a_f} \leq \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;
}