Cod sursa(job #2211047)

Utilizator giotoPopescu Ioan gioto Data 9 iunie 2018 11:48:29
Problema Barman Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <bits/stdc++.h>
using namespace std;

int n;
int a[605], b[605], f[605], aux[605], pos[605];
vector <int> p[605];
int main()
{
    freopen("barman.in", "r", stdin);
    freopen("barman.out", "w", stdout);

    scanf("%d", &n);
    for(int i = 1; i <= n ; ++i){
        scanf("%d", &a[i]);
        b[i] = a[i];
    }

    sort(b + 1, b + n + 1);
    for(int i = 1; i <= n ; ++i)
        a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;

    for(int i = 1; i <= n ; ++i) b[i] = a[i];
    sort(b + 1, b + n + 1);

    int Last = 0, val = 0;
    for(int i = 1; i <= n ; ++i){
        if(b[i] != Last) {
            Last = b[i];
            f[b[i]] = val + 1;
            b[i] = val + 1;
            val = b[i];
        }
        else b[i] = val;
    }
    for(int i = 1; i <= n ; ++i) a[i] = f[a[i]];


    int Sol = 2000000000;
    for(int i = 1; i <= n ; ++i){
        memcpy(aux, a, sizeof(a));
        memset(pos, 0, sizeof(pos));
        for(int i = 1; i <= n ; ++i)
            p[b[i]].clear();
        for(int i = 1; i <= n ; ++i)
            if(a[i] != b[i])p[b[i]].push_back(i);
        for(int i = 1; i <= n ; ++i)
            if(a[i] != b[i])a[i] = p[a[i]][pos[a[i]]++];
            else a[i] = 0;
        int cost = 0;
        for(int i = 1; i <= n ; ++i){
            int j = i, Last = 0;
            while(a[j] != j && a[j] != 0){
                cost += 20;
                int w = a[j];
                cost = cost + abs(w - j);
                a[j] = Last;
                Last = w; j = w;
            }
            a[j] = j;
        }
        if(cost < Sol) Sol = cost;
        memcpy(a, aux, sizeof(aux));
        int c = b[1];
        for(int i = 1; i < n ; ++i)
            b[i] = b[i + 1];
        b[n] = c;
    }
    printf("%d", Sol);
    return 0;
}