Cod sursa(job #1327104)

Utilizator PaueyPaula Nicoleta Gradu Pauey Data 26 ianuarie 2015 13:16:21
Problema Barman Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <cmath>

#include <algorithm>
#include <iostream>
#include <fstream>
#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 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 = ans + abs(a[j].pozs - dec) + 20;
            }
            //cout << a[j].pozs << ' ' << dec << '\n';
        }
        if(ans < cost) {
            cost = ans;
            fin = i;
        }
        //cout << i << ' ' << ans << '\n';
    }
    cout << cost << '\n';
    return 0;
}