a bit of greedy: UVa 10026 - Shoemaker's Problem

Problem Statement:
UVa 10026 - Shoemaker's Problem

Summary:
Given a list of jobs, we can only work on one job each day. Each job \(i\) takes \(t_i\) days to complete and for each day of not starting on the job, we must pay \(s_i\) fine. Once we start on a job, we will finish it before starting the next job. We are to find the best permutation/arrangement of the jobs that minimizes the total fine incurred.

Solution:
A great application of exchange argument that establishes the relationship that must hold in an optimal arrangement amongst all permutation. This optimization problem reduces to sorting problem.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

/* 
The correct greedy algo and its proof: sort by fine/time
Proof:
s is fine, t is days
Suppose that (s_1,t_1), (s_2,t_2), ..., (s_n,t_n) is the optimal
arrangement such that the total fine is the lowest. Hence we have
O = s_1 (0) + s_2 (t_1) + s_3 (t_1 + t_2) + ...
    + s_i (t_1 + t_2 + ... + t_{i-1})
    + s_{i+1} (t_1 + t_2 + ... + t_{i-1} + t_i) 
    + ...
Since O is optimal, by exchange argument, if we exchange the position of
s_i,t_i and s_{i+1},t_{i+1}, we will have total fine O' which will cannot be lower
than O:
O' = ... + s_{i+1} (t_1 + t_2 + ... + t_{i-1})
         + s_i (t_1 + t_2 + ... + t_{i-1} + t_{i+1})
         + ...
         
hence 
    O' - O >= 0 
        <=> s_{i+1} (-t_i) + s_i (t_{i+1}) >= 0
        <=> s_i/t_i >= s_{i+1}/t_{i+1}

Hence in the optimal arrangement, s_i comes before s_{i+1} iff s_i/t_i >= s_{i+1}/t_{i+1}
*/

vector<int> arr, s, t;

bool comp(const int& L, const int& R){
    if(s[L] * t[R] == s[R] * t[L]) return L < R;
    return s[L] * t[R] < s[R] * t[L];
}

int main(){
    int TC;
    cin >> TC;
    bool flag = false;
    while(TC--){
        if(flag) printf("\n");
        flag = true;
        int N;
        cin >> N;
        arr.clear();
        s.clear();
        t.clear();
        for(int i=0;i<N;++i){
            int u,v;
            cin >> u >> v;
            s.push_back(u);
            t.push_back(v);
            arr.push_back(i);
        }
        sort(arr.begin(), arr.end(), comp);
        for(int i=0;i<N;++i){
            if(i != 0) printf(" ");
            printf("%d", arr[i]+1);
        }
        printf("\n");
    }
    return 0;
}