2569번: 짐정리

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


$O(n)$

수열을 정렬하면 처음위치 -> 나중위치간 간선을 만들어 그래프를 만들 수 있다.
만들어진 그래프는 몇 개의 사이클로 만들어질 것이다.
각 사이클마다 존재하는 짐을 정리하기 위해 다음 두 가지 방법 중 최소의 힘이 들어가는 방법을 사용한다.

1. 사이클 내 최소 짐을 가지고 옮겨가며 사이클 내 모든 짐을 정리한다.
2. 전체 짐 중 최소 짐과 사이클 내 최소 짐의 자리를 바꾼 뒤 이를 이용해 사이클 내 모든 짐을 정리한다. 이후 처음에 자리를 바꾼 두 짐을 다시 바꾼다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, ck[1000], r;
pair<int, int> p[1000];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &p[i].first), p[i].second = i;
    sort(p, p + n);
    for (int i = 0; i < n; i++) {
        if (ck[i]) continue;
        int c = 0;
        for (int j = i; !ck[j]; j = p[j].second) {
            ck[j] = 1;
            r += p[j].first;
            c++;
        }
        r += min(p[0].first*(c + 1) + p[i].first, p[i].first*(c - 2));
    }
    printf("%d", r);
    return 0;
}