6223번: Cow Sorting

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


참고로 koi 2007 지역 본선 중등 4 번과 같은 문제

#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAX_N = 10000;
int mini, p[100001], n, g[MAX_N], res;
bool ck[MAX_N];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int a;
        scanf("%d", &g[i]);
        p[g[i]] = i;
        res += g[i];
    }
    mini = *min_element(g, g + n);
    sort(g, g + n);
    for (int i = 0; i < n; i++) {
        if (ck[i]) continue;
        int h = i, cnt = 0, s = 1e6;
        do {
            ck[h] = true;
            s = min(s, g[h]);
            h = p[g[h]];
            cnt++;
        } while (!ck[h]);
        res += min((cnt - 2)*s, s + (cnt + 1)*mini);
    }
    printf("%d", res);
    return 0;
}