UVA 10026 Shoemaker's Problem ( Greedy )

UVa Online Judge
先想像一個最佳排列已經出來了。那麼任意相鄰的工作交換後不會影響其他工作，所以我們考慮這個已經是最優的排列中的相鄰工作是怎麼排出來的。假設現在這兩個工作分別是 a和 b，那麼
先排 a再排 b的總花費是 ( a.duration * a.fine + ( a.duration + b.duration ) * b.fine )
先排 b再排 a的總花費是 ( b.duration * b.fine + ( b.duration + a.duration ) * a.fine )
不難發現先排 a一定比較好的情況是 a.duration * b.fine < b.duration * a.fine。所以只要依據這個性質做排序就可以了。要注意的是，題目要求若有多解需按字典序排序，不同測資之間也需要空行。
碎念：傻了我竟然寫成 for( i = 0; i < n; ++i ) printf("%d%c", job[ i ].id, i == n ? '\n' : ' '); ，完全不會換行。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 3;

struct Job{
    int id, duration, fine;
    void read(int _id){
        id = _id;
        scanf("%d%d", &duration, &fine);
    }
} job[MAXN];

bool cmp(const Job &a, const Job &b){
    int fine4afirst = a.duration * b.fine;
    int fine4bfirst = b.duration * a.fine;
    if( fine4afirst == fine4bfirst ) return a.id < b.id;
    return fine4afirst < fine4bfirst;
}

int n;

int main(){
    int T; scanf("%d", &T);
    while( T-- ){
        scanf("%d", &n);
        for(int i = 0; i < n; ++i)
            job[ i ].read( i + 1 );
        sort( job, job + n, cmp );
        for(int i = 0; i < n; ++i)
            printf("%d%c", job[ i ].id, i == n - 1 ? '\n' : ' '); // 竟然寫成 i == n。。
        if( T ) puts("");
    }
    return 0;
}