Cod sursa(job #2725113)

Utilizator theo2003Theodor Negrescu theo2003 Data 18 martie 2021 14:15:47
Problema Barman Scor 0
Compilator cpp-64 Status done
Runda simularesimulare Marime 0.92 kb
#include <algorithm>
#include <fstream>
#include <set>
#include <map>
using namespace std;
ifstream cin("barman.in");
ofstream cout("barman.out");
int n, a[601], b[601];
long long mn = (1ll<<60);
map<int, pair<vector<int>, int> > p;
long long findmin() {
    long long out = n * 20;
    p.clear();
    for(int x = 0; x<n; x++){
        if(a[x] != b[x]){
            p[a[x]].first.push_back(x);
        }else out -= 20;
    }
    for(int x = 0;x<n;x++){
        if(a[x] != b[x]){
            out += abs(p[b[x]].first[p[b[x]].second] - x);
            p[b[x]].second++;
        }
    }
    return out;
}
int main() {
    cin>>n;
    for(int x = 0; x<n; x++) {
        cin>>a[x];
        b[x] = a[x];
    }
    sort(a, a + n);
    for(int x = 0; x<n; x++) {
        mn = min(mn, findmin());
        for(int y = 1; y<n; y++)
            swap(a[y], a[y - 1]);
    }
    cout<<mn<<'\n';
    return 0;
}