Pagini recente » Cod sursa (job #19379) | Cod sursa (job #280264) | Cod sursa (job #48245) | Cod sursa (job #19243) | Cod sursa (job #112209)
Cod sursa(job #112209)
//#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;
}