Cod sursa(job #1327502)

Utilizator PaueyPaula Nicoleta Gradu Pauey Data 26 ianuarie 2015 19:48:37
Problema Barman Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <cmath>

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

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

vector<pahar> v;

int N;

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

vector<int> v1, v2;
bool viz[MAXN];

int solve() {
   int ans = 0;
   for(int i = 0; i < v1.size(); ++i)
      viz[i] = 0;
   for(int i = 0; i < v1.size(); ++i) {
      int cur = i;
      while(!viz[cur]) {
         viz[cur] = 1;
         ans += abs(v1[cur] - v2[cur]);
         for(int j = 0; j < v1.size(); ++j) {
            if(v1[j] == v2[cur]) {
               cur = j;
               break;
            }
         }
      }
   }
   return ans;
}

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) {
        pahar p;
        cin >> p.val;
        p.pozi = p.pozs = p.pozd = i;
        if(v.empty() || p.val != v[v.size() - 1]) {
            v.push_back(p);
        }
        else {
            ++v[v.size() - 1].pozd;
        }
    }
    sort(v.begin(), v.end(), cmp);
    for(int i = 1; i <= N; ++i) {
        long long ans = 0;
        v1.clear();
        v2.clear();
        for(int j = 1; j <= N; ++j) {
            int dec = (j + i - 1) % N;
            if(!dec)
                dec = N;
            if(dec >= a[j].pozs  && dec <= a[j].pozd) {
                a[j + 1].pozs = dec + 1;
                continue;
            }
            else {
                ans += 20;
                v1.push_back(a[j].pozi);
                v2.push_back(dec);
            }
        }
        ans += solve();
        if(ans < cost) {
            cost = ans;
            fin = i;
        }
    }
    cout << cost << '\n';
    return 0;
}