1900번: 레슬러

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


$O(n\lg n)$

(힘,마술링 힘)이 주어졌을 때
(xi,yi)가 (xj,yj)를 이길 조건은 xi+yi*xj > xj+yj*xi
이 조건은 xi/(yi-1) < xj/(yj-1)일 조건과 동치이다.
(yi=1이면 해당 항이 무한대로 간다고 가정하자. 이러한 레슬러는 문제 조건에 따라 많아야 하나 존재한다.)
즉, xi/(yi-1) 값에 따라 모든 레슬러의 순위를 결정할 수 있으므로 그 순위와 반대로 동호와 만나게 하면 금화가 최소로 든다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n;
struct st {
    int x, y, idx;
}a[10001];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i].x, &a[i].y);
        a[i].idx = i;
    }
    sort(a + 1, a + 1 + n, [](st i, st j) {return i.x + i.y*j.x > j.x + j.y*i.x; });
    for (int i = 1; i <= n; i++) printf("%d\n", a[i].idx);
    return 0;
}