Cod sursa(job #1327134)

Utilizator PaueyPaula Nicoleta Gradu Pauey Data 26 ianuarie 2015 13:36:11
Problema Barman Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <cmath>

#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#define MAXN 606
using namespace std;

struct pahar {
    int val, pozs, pozd;
};

pahar a[MAXN];

int N;

bool cmp(pahar x, pahar y) {
    if(x.val == y.val)
        return x.pozs < y.pozs;
    return x.val < y.val;
}

int son[MAXN];
bool viz[MAXN];

int main()
{
    ifstream cin("barman.in");
    ofstream cout("barman.out");
    int fin = 0;
    long long cost = (1 << 30);
    cin >> N;
    for(int i = 1; i <= N; ++i) {
        cin >> a[i].val;
        a[i].pozs = a[i].pozd = i;
        if(a[i].val == a[i - 1].val) {
            a[i].pozs = a[i - 1].pozs;
            a[i - 1].pozd = a[i].pozd;
        }
    }
    sort(a + 1, a + N + 1, cmp);
    for(int i = 1; i <= N; ++i) {
        long long ans = 0;
        for(int j = 1; j <= N; ++j) {
            int dec = (j + i - 1) % N;
            if(!dec)
                dec = N;
            if(dec <= a[j].pozd && dec >= a[j].pozs) {
                continue;
            }
            else {
                ans += 20;
                //son[j] = dec;
                if(abs(a[j].pozs - dec) < abs(a[j].pozd - dec)) {
                    if(a[j].val == a[j + 1].val) {
                        ++a[j + 1].pozs;
                    }
                    ans += abs(a[j].pozs - dec);
                }
                else {
                    if(a[j].val == a[j + 1].val) {
                        --a[j + 1].pozd;
                    }
                    ans += abs(a[j].pozd - dec);
                }
                //ans = ans + min(abs(a[j].pozs - dec), abs(a[j].pozd - dec));
            }
        }
        if(ans < cost) {
            cost = ans;
            fin = i;
        }
        //cout << i << ' ' << ans << '\n';
    }
    cout << cost << '\n';
    return 0;
}