test/aoj_alds_6_D.test.cpp

• View this file on GitHub
• Last update: 2022-07-30 20:12:45+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/6/ALDS1_6_D

Depends on

• Cyclic Permutation(巡回置換分解) (src/algorithm/Cyclic-Permutation.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/6/ALDS1_6_D"

#include <iostream>
#include "../src/algorithm/Cyclic-Permutation.hpp"

int main() {
    int n;
    std::cin >> n;
    std::vector<int> ws(n);
    for (auto& w : ws) std::cin >> w;
    int allmin = 1000000;
    for (auto w : ws) allmin = std::min(allmin, w);
    auto cycles = zawa::decomp_cyclic_permutation(ws);
    int ans = 0;

    for (auto cycle : cycles) {
        int inval = 0;
        int outval = 0;
        int inmin = 1000000;
        for (auto c : cycle) inmin = std::min(inmin, ws[c]);
        for (auto c : cycle) inval += ws[c];
        inval += inmin * (cycle.size() - 2);
        for (auto c : cycle) outval += ws[c];
        outval -= inmin;
        outval += allmin * (cycle.size() - 1);
        outval += 2 * (allmin + inmin);
        ans += std::min(outval, inval);
    }

    std::cout << ans << std::endl;
}

#line 1 "test/aoj_alds_6_D.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/6/ALDS1_6_D"

#include <iostream>
#line 2 "src/algorithm/Cyclic-Permutation.hpp"

#include <vector>
#include <algorithm>

namespace zawa {

    template <typename T>
    std::vector<std::vector<int>> decomp_cyclic_permutation(std::vector<T>& arr) {
        std::vector<std::pair<T, int>> cp(arr.size());
        for (int i = 0 ; i < (int)arr.size() ; i++) {
            cp[i] = {arr[i], i};
        }
        sort(cp.begin(), cp.end());

        std::vector<std::vector<int>> res;
        std::vector<int> used(arr.size());
        for (int i = 0 ; i < (int)arr.size() ; i++) {
            if (used[i]) continue;
            std::vector<int> cycle;
            int now = i;
            while(!used[now]) {
                cycle.emplace_back(now);
                used[now] = 1;
                now = cp[now].second;
            }
            res.emplace_back(cycle);
        }

        return res;
    }

}// namespace zawa
#line 5 "test/aoj_alds_6_D.test.cpp"

int main() {
    int n;
    std::cin >> n;
    std::vector<int> ws(n);
    for (auto& w : ws) std::cin >> w;
    int allmin = 1000000;
    for (auto w : ws) allmin = std::min(allmin, w);
    auto cycles = zawa::decomp_cyclic_permutation(ws);
    int ans = 0;

    for (auto cycle : cycles) {
        int inval = 0;
        int outval = 0;
        int inmin = 1000000;
        for (auto c : cycle) inmin = std::min(inmin, ws[c]);
        for (auto c : cycle) inval += ws[c];
        inval += inmin * (cycle.size() - 2);
        for (auto c : cycle) outval += ws[c];
        outval -= inmin;
        outval += allmin * (cycle.size() - 1);
        outval += 2 * (allmin + inmin);
        ans += std::min(outval, inval);
    }

    std::cout << ans << std::endl;
}

Back to top page