Cod sursa(job #2710242)

Utilizator PatrickCplusplusPatrick Kristian Ondreovici PatrickCplusplus Data 22 februarie 2021 11:26:43
Problema Barman Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("barman.in");
ofstream fout("barman.out");

const int nmax = 605;
int n, v[nmax], v2[nmax], v3[nmax];
vector <int> G[nmax], G2[nmax];

struct idk{
    int val, id;
    bool operator < (const idk &a) const{
        return a.val > val;
    }
}aux[nmax];

void normalizare(){
    sort(aux + 1, aux + n + 1);
    int z = 1;
    v[aux[1].id] = z;
    v3[aux[1].id] = z;
    for (int i = 2; i <= n; ++i){
        if (aux[i].val != aux[i - 1].val){
            ++z;
        }
        v[aux[i].id] = z;
        v3[aux[i].id] = z;
    }
}

int main(){
    fin >> n;
    for (int i = 1; i <= n; ++i){
        fin >> v[i];
        aux[i] = {v[i], i};
    }
    normalizare();
    sort(v3 + 1, v3 + n + 1);
    int minim = 1e9;
    for (int i = 1; i <= n; ++i){
        int k = 1;
        for (int j = i + 1; j <= n; ++j){
            v2[j] = v3[k++];
        }
        for (int j = 1; j <= i; ++j){
            v2[j] = v3[k++];
        }
        int ans = 0;
        for (int j = 1; j <= n; ++j){
            if (v[j] != v2[j]){
                G[v[j]].push_back(j);
                G2[v2[j]].push_back(j);
                ans += 20;
            }
        }
        for (int j = 1; j <= n; ++j){
            for (int j2 = 0; j2 < G[j].size(); ++j2){
                ans += abs(G2[j][j2] - G[j][j2]);
            }
        }
        minim = min(minim, ans);
        for (int j = 1; j <= n; ++j){
            G[j].clear();
            G2[j].clear();
        }
    }
    fout << minim;
    fin.close();
    fout.close();
    return 0;
}