Cod sursa(job #2727612)

Utilizator Iulia25Hosu Iulia Iulia25 Data 22 martie 2021 10:37:15
Problema Barman Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

int n, r = 2e9, k, K;
int val[605];
vector <int> poz[605], P[605];
pair <int, int> a[605];

int main()  {
    cin >> n;
    for (int i = 1; i <= n; ++i)    {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort (a + 1, a + n + 1);
    for (int i = 1; i <= n; ++i)    {
        if (a[i].first > a[i - 1].first)
            ++k;
        poz[k].push_back(a[i].second);
        val[a[i].second] = k;
    }
    K = k;
    for (int start = 1; start <= n; ++start)    {
        int ans = 0;
        k = 1;
        for (int i = 1; i <= n; ++i)    {
            int p = (i + start - 1);
            if (p > n)
                p -= n;
            if (P[k].size() == poz[k].size())
                ++k;
            P[k].push_back(p);
            if (k != val[p])
                ans += 20;
        }
        for (int k = 1; k <= K; ++k)    {
            sort (P[k].begin(), P[k].end());
            for (int i = 0; i < poz[k].size(); ++i)
                ans += abs(poz[k][i] - P[k][i]);
            P[k].clear();
        }
        r = min(r, ans);
    }
    cout << r;
    return 0;
}