(14908) 구두 수선공

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

단계별로 풀어보기

42단계(그리디 알고리즘 2) 5번째

 

 

 

ATM에서 간단하게 설명했던 Exchange argument 기법을 더 적극적으로 사용하는 문제.

어떤 두 사람 i, j에 대해 x초에 i→j 순서로 일을 했을 때와 j→i 순서로 일을 했을 때 보상금은 아래와 같다.

1) i→j일 때 i에게 주는 보상금은 x*Si, j에게 주는 보상금은 (x+Ti)*Sj

2) j→i일 때 j에게 주는 보상금은 x*Sj, i에게 주는 보상금은 (x+Tj)*Si

같은 값은 비교 의미가 없으니 빼고 다른 값만 비교하면 첫 번째의 보상금은 Ti*Sj, 두 번째의 보상금은 Tj*Si이다.

Ti+Tj=Tj+Ti이므로 두 사람 순서가 바뀌어도 앞뒤 사람들의 보상금에는 영향이 없다.

따라서 이 값이 작은 순서대로 정렬을 하면 된다.

 

사실 이 정렬 순서는 시간 대비 보상금(Ti/Si)을 기준으로 정렬한 것과 같은데, 실수 자료형을 피하고 (이 문제는 아니지만) Si가 0인 경우를 대비해 교차 곱셈 형태로 정렬한 것이다. 이렇게 두 요소가 섞여 있어도 정렬의 수학적 규칙인 추이성과 비대칭성만 만족한다면 상관이 없다.

 

 

 

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

int main() 
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector<pair<int,pair<int,int>>> v(n);
  
  for(int i=0;i<n;i++){
    cin >> v[i].second.first >> v[i].second.second;
    v[i].first= i+1;
  }
  
  sort(v.begin(), v.end(), [](auto A, auto B){
    int Ares= A.second.first*B.second.second;
    int Bres= B.second.first*A.second.second;
    
    if(Ares!=Bres)  return Ares<Bres;
    return A.first<B.first;
  });
  
  for(auto elem:v)  cout << elem.first << " ";
  
  return 0;
}