Cod sursa(job #2058913)

Utilizator retrogradLucian Bicsi retrograd Data 6 noiembrie 2017 13:54:52
Problema Barman Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <bits/stdc++.h>

using namespace std;

int Solve2(vector<int> A, vector<int> B) {
    int n = B.size(), ans = 0;
    for (int i = 0; i < n; ++i)
        ans += 20 + abs(B[i] - A[i]);
    return ans;
}

int Solve(vector<int> A, vector<int> B) {
    int n = A.size();
    
    map<int, vector<int>> PA, PB;
    set<int> vals;

    for (int i = 0; i < n; ++i) {
        if (A[i] == B[i]) continue;
        PA[A[i]].push_back(i);
        PB[B[i]].push_back(i);
        vals.insert(A[i]);
    }

    int ans = 0;
    for (auto val : vals) {
        ans += Solve2(PA[val], PB[val]);
    }
    return ans;
}

int main() {
    ifstream cin("barman.in");
    ofstream cout("barman.out");

    int n; cin >> n;
    vector<int> A(n), B(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
        B[i] = A[i];
    }

    int ans = 1e9;
    sort(B.begin(), B.end());
    for (int it = 0; it < n; ++it) {
        ans = min(ans, Solve(A, B));
        rotate(B.begin(), B.begin() + 1, B.end());
    }
    cout << ans << endl;
}