[14908] 구두 수선공

https://www.acmicpc.net/problem/14908

14908번: 구두 수선공

<문제>

일의 효율(우선순위)을 (s / t)=d로 놓은 뒤, d가 내림차순이 되도록 정렬한다.

d가 같은 경우에는 idx가 오름차순이 되도록 한 뒤, 인덱스를 출력하면 되겠다.

이 문제에 적용된 "Exchange argument"에 대해서 설명한 좋은 글이 있으니, 이 문제를 풀때 참고해보면 좋겠다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, ans;
vector<pair<double, int>> v;
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    v.resize(n);
    int i;
    for (i = 0; i < n; i++) {
        int t, s;
        double d;
        cin >> t >> s;
        d = (double)s / (double)t;
        v[i] = {d, i + 1};
    }
    sort(v.begin(), v.end(), [](auto x, auto y) -> bool {
        if (abs(x.first - y.first) < (double)1e-9) return x.second < y.second;
        return x.first > y.first;
    });
    for (auto& i : v) cout << i.second << " ";
    return 0;
}