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