７．７ 最小コストソート

最小値を使って交換し、その上で計算式の算出と反例まで考えないと解けない難問。とても難しいので今回は写経です。本書内の回答例は変数名がかなり分かりづらいので、ちょっと直してはいます。また、ソート済のテーブルの先頭の値が最小値なので、そのまま使っています(B[0])。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

static void inputArray(int A[], int num) {
  for (int i = 0; i < num; i++) {
    cin >> A[i];
   }
}

static void printArray(int A[], int num) {
  for (int i = 0; i < num; i++) {
    cout << ((i != 0) ? " " : "") << A[i];
  }
  cout << endl;
}

static const size_t NMAX = 1000;
static const size_t VMAX = 10000;

static vector<int> A(NMAX), B(NMAX);
static vector<int> TABLE(VMAX + 1, 0);
static vector<bool> SORTED(NMAX, false);

static inline void printArray(vector<bool>& A, int num) {
  for (int i = 0; i < num; i++) {
    cout << ((i == 0) ? "" : " ") << A[i];
  } 
  cout << endl;
}

static inline int solve(int A[], int num) {
  B.assign(&A[0], &A[num]);
  sort(B.begin(), B.end());

  for (int i = 0; i < num; i++) {
    TABLE[B[i]] = i;
  }

  int ans = 0;
  for (int i = 0; i < num; i++) {
    if (SORTED[i]) {
      continue;
    }
    
    int cursor = i;
    int total = 0;
    int min = VMAX;
    int numInCycle = 0;
    while (true) {
      SORTED[cursor] = true;
      numInCycle++;
      min = std::min(min, A[cursor]);
      total += A[cursor];
      cursor = TABLE[A[cursor]];
      if (SORTED[cursor]) {
        break;     
      }
    }
    ans += std::min(total + (numInCycle - 2) * min, min + total + (numInCycle + 1) * B[0]);
  }

  return ans;
}

int main() {
  int n;
  cin >> n;

  inputArray(&A[0], n);

  const int ans = solve(&A[0], n);
  
  cout << ans << endl;

  return 0;
}