Cod sursa(job #1327084)

Utilizator dariusdariusMarian Darius dariusdarius Data 26 ianuarie 2015 13:00:16
Problema Barman Scor 10
Compilator cpp Status done
Runda simulareoji2015 Marime 1.54 kb
#include <algorithm>
#include <deque>
#include <fstream>
#include <vector>
using namespace std;
const int MAX_N = 666;

int n, a[MAX_N];
deque<int> poz[MAX_N];

inline int solve(int start) {
    vector< pair<int, int> > v;
    vector<int> q;
    for (int i = start; i <= n; ++ i) {
        v.push_back(make_pair(a[i], i));
        q.push_back(a[i]);
    }
    for (int i = 1; i < start; ++ i) {
        v.push_back(make_pair(a[i], i));
        q.push_back(a[i]);
    }
    sort(q.begin(), q.end());
    for (int i = 1; i <= n; ++ i) {
        poz[i].clear();
    }
    for (int i = 0; i < n; ++ i) {
        poz[v[i].first].push_back(i);
    }
    int answer = 0;
    for (int i = 0; i < n; ++ i) {
        if (v[i].first == q[i]) {
            poz[v[i].first].pop_front();
        } else {
            answer += 40 + 2 * abs(v[i].second - v[poz[q[i]].front()].second);
            swap(v[i], v[poz[q[i]].front()]);
            poz[q[i]].pop_front();
        }
    }
    return answer;
}

int main() {
    ifstream fin("barman.in");
    ofstream fout("barman.out");
    vector<int> v;
    fin >> n;
    for (int i = 1; i <= n; ++ i) {
        fin >> a[i];
        v.push_back(a[i]);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (int i = 1; i <= n; ++ i) {
        a[i] = upper_bound(v.begin(), v.end(), a[i]) - v.begin();
    }
    int cost = 1.e9;
    for (int i = 1; i <= n; ++ i) {
        cost = min(cost, solve(i));
    }
    fout << cost << "\n";
    return 0;
}