구두 수선공 (JUNGOL 6271)

 

https://jungol.co.kr/problem/6271

---

아이디어

Exchange Argument를 이용해봅시다.

어떠한 순서에서 i번째 작업과 i+1번째 작업을 비교해봅시다.

현재 i번째 작업이 끝나는 시점이 t라고 하면, i+1번째 작업이 끝나는 시점은 t+T_i+1이며, 보상금은 V₁=t*S_i+(t+T_i+1)*S_i+1입니다. 만약 두 작업의 순서를 바꾼다면 보상금은 V₂=(t+T_i+1-T_i)*S_i+1+(t+T_i+1)*S_i입니다. V₁-V₂를 해주면 T_i*S_i+1-T_i+1*S_i가 됩니다. 이 값이 음수가 되도록 순서를 유지시켜주어야하므로 S_i/T_i가 증가하는 순서대로 작업을 배치해주면 됩니다.

---

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#define ll long long
using namespace std;

bool cmp(array <ll,3> A,array <ll,3> B)
{
    if (A[2]*B[1]!=A[1]*B[2]) return A[2]*B[1]>A[1]*B[2];
    return A[0]<B[0];
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,i,a,b;
    vector <array <ll,3> > v;

    cin>>N;
    for (i=1;i<=N;i++)
    {
        cin>>a>>b;
        v.push_back({i,a,b});
    }

    sort (v.begin(),v.end(),cmp);

    for (i=0;i<N;i++)
        cout<<v[i][0]<<' ';
}