Cod sursa(job #1744460)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 19 august 2016 20:40:29
Problema Barman Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include<fstream>
#include<algorithm>
#include<vector>
#include<cstring>
#define DIM 605
using namespace std;
int n, i, ii, nr, sum, sol, st, dr, mid, aux, nr1;
int v[DIM], w[DIM], f[DIM], r[DIM], u[DIM];
vector<int> poz[DIM];
ifstream fin("barman.in");
ofstream fout("barman.out");
int modul(int x){
    if(x > 0){
        return x;
    }
    return -x;
}
int main(){
    fin>> n;
    for(i = 1; i <= n; i++){
        fin>> v[i];
        w[i] = v[i];
    }
    sort(w + 1, w + n + 1);
    nr = 1;
    for(i = 2; i <= n; i++){
        if(w[i] != w[nr]){
            w[++nr] = w[i];
        }
    }
    for(i = 1; i <= n; i++){
        st = 1;
        dr = nr;
        while(st <= dr){
            mid = (st + dr) / 2;
            if(v[i] == w[mid]){
                break;
            }
            else{
                if(v[i] > w[mid]){
                    st = mid + 1;
                }
                else{
                    dr = mid - 1;
                }
            }
        }
        v[i] = mid;
        f[mid]++;
    }
    for(i = 1; i <= nr; i++){
        while(f[i] != 0){
            r[++nr1] = i;
            f[i]--;
        }
    }
    sol = 1000000000;
    for(ii = 1; ii < n; ii++){
        sum = 0;
        for(i = 1; i <= nr; i++){
            poz[i].clear();
            u[i] = 0;
        }
        memset(f, 0, sizeof(f));
        for(i = 1; i <= n; i++){
            if(v[i] == r[i]){
                f[i] = 1;
            }
            else{
                poz[ r[i] ].push_back(i);
            }
        }
        for(i = 1; i <= n; i++){
            if(f[i] == 0){
                sum += 20;
                sum += modul(i - poz[ v[i] ][ u[ v[i] ] ]);
                u[ v[i] ]++;
            }
        }
        sol = min(sol, sum);
        aux = r[n];
        for(i = n - 1; i >= 1; i--){
            r[i + 1] = r[i];
        }
        r[1] = aux;
    }
    fout<< sol <<"\n";
    return 0;
}