Cod sursa(job #413313)

Utilizator freak93Adrian Budau freak93 Data 8 martie 2010 08:39:38
Problema Barman Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<fstream>
#include<algorithm>
#include<map>
#include<list>

using namespace std;

const char iname[]="barman.in";
const char oname[]="barman.out";
const int maxn=605;

ifstream f(iname);
ofstream g(oname);

int a[maxn],s[maxn*2],i,j,n,mint=(1<<31)-1;

map<int,list<int> > M;

int mod(int a)
{
    return a<0?-a:a;
}

void test(int *a,int *b)
{
    M.erase(M.begin(),M.end());
    int cost=0;
    for(i=1;i<=n;++i)
        if(a[i]!=b[i])
            cost+=20,M[a[i]].push_back(i);

    for(i=1;i<=n;++i)
        if(a[i]!=b[i])
            cost+=mod(i-M[b[i]].front()),M[b[i]].pop_front();
    if(cost<mint)
        mint=cost;
}

int main()
{
    f>>n;
    for(i=1;i<=n;++i)
        f>>a[i],s[i]=a[i];
    sort(s+1,s+n+1);
    for(i=1;i<=n;++i)
        s[i+n]=s[i];

    for(j=1;j<=n;++j)
        test(a,s+j-1);

    g<<mint<<"\n";

    f.close();
    g.close();

    return 0;
}