POI 2 Stage 3 Job Scheduling ( Greedy, Math )

http://main.edu.pl/en/archive/oi/2/sze

題意：
有 N 個工作，假設當前時間已經過 T 單位，那麼工作 i 需要花費的時間為 A[ i ] * T + B[ i ]。一次只能做一個工作，問最短時間完成的工作序列。

資料規模：
In the first line of the standard input there is one positive integer not greater then 10000. It is the number of jobs .
In each of the following n lines there is a pair of nonnegative real numbers. The numbers are written in a standard form with a decimal point and six digits after the point. The numbers are separated by a single space. It is the pair of coefficients ai and bi determining the dependence of the execution time of the corresponding -th job upon the time it starts.

解法：
考慮兩個相鄰的工作交換，會有什麼樣的影響。顯然這兩個工作以外的工作的貢獻都不會有變化。列一下不等式會發現當 a[ i + 1 ] * b[ i ] ≤ a[ i ] * b[ i + 1 ]，將之交換一定不會比較好，而反之則交換一定更好。因此顯然依照這個比較方式做成非遞減即最優。

時間 / 空間複雜度：
O( N lg N ) / O( N )

#include <bits/stdc++.h>
using namespace std;

const int MAXN =  10000;

int N;
pair< double, double > job[ MAXN ];

int ord[ MAXN ];

bool cmp( int i, int j ){
  return job[ j ].first * job[ i ].second < job[ i ].first * job[ j ].second;
}

signed main(){
  ios::sync_with_stdio( 0 );
  int N; cin >> N;
  for( int i = 0; i < N; ++i ){
    cin >> job[ i ].first >> job[ i ].second;
    ord[ i ] = i;
  }
  sort( ord, ord + N, cmp );
  for( int i = 0; i < N; ++i ){
    cout << ord[ i ] + 1 << "\n";
  }
  return 0;
}