Cod sursa(job #2380482)

Utilizator Andrei1998Constantinescu Andrei-Costin Andrei1998 Data 15 martie 2019 01:35:16
Problema Barman Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <bits/stdc++.h>

using namespace std;

typedef long long int lint;

lint solve(const vector <int> &v, vector <int> &goal) {
    const int N = v.size();
    map <int, vector <int> > where;
    for (int i = 0; i < N; ++i) {
        if (goal[i] != v[i]) {
            where[goal[i]].push_back(i);
        }
    }
    lint cost = 0;
    for (int i = N - 1; i >= 0; --i) {
        if (goal[i] != v[i]) {
            cost += 20;
            const int dest = where[v[i]].back(); where[v[i]].pop_back();
            cost += abs(i - dest);
        }
    }
    return cost;
}

int main() {
    ifstream cin("barman.in");
    ofstream cout("barman.out");
    int N;
    cin >> N;
    vector <int> v(N), goal(N);
    for (int i = 0; i < N; ++i) {
        cin >> v[i]; goal[i] = v[i];
    }
    sort(goal.begin(), goal.end());
    lint ans = numeric_limits <lint> :: max();
    for (int d = 0; d < N; ++d) {
        ans = min(ans, solve(v, goal));
        rotate(goal.begin(), goal.begin() + 1, goal.end());
    }
    cout << ans << endl;
    return 0;
}