백준 14908 / C++

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

14908번: 구두 수선공

 

[ 풀이 ] 

(T1 S1) (T2 S2) ... (Tn Sn) 이 최적해라고 가정하자. 

이제 (T1 S1) (T2 S2)를 교환했을 때 값을 구해서 비교하자.

양식의 차를 비교하면 1식-2식 = T1S2-T2S1이 되고 최적해조건에 따라  T1S2 < T2S1을 만족해야 한다.

즉, T1/S1 < T2/S2 이다. 

중간에 있는 (Ti Si)와 (Ti+1, Si+1)을 교환했을 때도 다 소거되고 마찬가지로 위와 같은 차이만 남게된다. 

따라서 T/S를 오름차순 정렬한 인덱스가 답이 된다.

 

[ Code ]

#include <bits/stdc++.h>
using namespace std;
pair<double, int> a[1001];

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	for (int i = 0; i < n; i++) {
		double T, S; cin >> T >> S;
		a[i] = { T / S , i + 1 };
	}
	sort(a, a + n);
	for (int i = 0; i < n; i++) {
		cout << a[i].second << " ";
	}
}