Cod sursa(job #112208)

Utilizator stef2nStefan Istrate stef2n Data 3 decembrie 2007 19:34:52
Problema Barman Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 kb
//#define DEBUG

#include <cstdio>
#include <algorithm>
#include <vector>
#ifdef DEBUG
#include <iostream>
#endif
using namespace std;

#define NMAX 600
#define INF 1000000000

int N, value[NMAX];
int ind[NMAX];
int CMIN=INF;

inline bool cmp(int i, int j)
{
    if(value[i]!=value[j])
        return value[i]<value[j];
    else
        return i<j;
}

inline int get_cost(int a, int b)
{
    if(a==b)
        return 0;
    if(a<b)
        return 20+min(b-a,a+N-b);
    return 20+min(a-b,b+N-a);
}

int mincost(const vector <int> &v, const vector <int> &w)
{
#ifdef DEBUG
    cerr<<"Pozitiile: ";
    for(unsigned int i=0; i<v.size(); ++i)
        cerr<<v[i]<<" ";
    cerr<<"trebuie cuplate cu pozitiile: ";
    for(unsigned int i=0; i<w.size(); ++i)
        cerr<<w[i]<<" ";
    cerr<<endl;
#endif
    if(v.empty())
        return 0;
    int cost=INF;
    for(unsigned int i=0; i<v.size(); ++i)
    {
        int c=0;
        for(unsigned int j=i; j<w.size(); ++j)
            c+=get_cost(v[j-i],w[j]);
        for(unsigned int j=0; j<i; ++j)
            c+=get_cost(v[w.size()-i+j],w[j]);
        if(cost>c)
            cost=c;
    }
    return cost;
}


int main()
{
    freopen("barman.in","r",stdin);
    freopen("barman.out","w",stdout);
    scanf("%d",&N);
    for(int i=0; i<N; ++i)
    {
        scanf("%d",&value[i]);
        ind[i]=i;
    }
    sort(ind, ind+N, cmp);
    for(int i=0, start=0; i<N; ++i, start=(start-1+N)%N)
    {
        int cost=0;
        vector <int> v, w;
        v.clear(); w.clear();
        for(int j=start, cnt=0; cnt<N; j=(j+1)%N, ++cnt)
        {
            if(!cnt || value[ind[j]]!=value[ind[(j-1+N)%N]])
            {
//                sort(w.begin(),w.end());
                if(!w.empty())
                    for(int k=0; k<N; ++k)
                    {
                        if(value[ind[k]]!=value[k] && value[k]==value[ind[w[0]]])
                            v.push_back(k);
                    }
                else
                    v.clear();
                if(cnt)
                    cost+=mincost(v,w);
                v.clear();
                w.clear();
            }
            if(value[ind[j]]!=value[j])
                w.push_back(j);
        }
        if(!w.empty())
            for(int k=0; k<N; ++k)
            {
                if(value[ind[k]]!=value[k] && value[k]==value[ind[w[0]]])
                    v.push_back(k);
            }
        else
            v.clear();
        cost+=mincost(v,w);
        if(CMIN>cost)
            CMIN=cost;
        int tmp=ind[0];
        for(int j=0; j<N-1; ++j)
            ind[j]=ind[j+1];
        ind[N-1]=tmp;
#ifdef DEBUG
        cerr<<endl;
#endif
    }
    printf("%d\n",CMIN);
    return 0;
}