Pagini recente » Cod sursa (job #2067422) | Cod sursa (job #2217884) | Cod sursa (job #500562) | Cod sursa (job #489615) | Cod sursa (job #112179)
Cod sursa(job #112179)
#include <cstdio>
#include <algorithm>
#include <vector>
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)
{
if(v.empty())
return 0;
int cost=INF;
for(unsigned int i=0; i<v.size(); ++i)
{
int c=0;
for(unsigned int j=w.size()-i; j<w.size(); ++j)
c+=get_cost(v[i+j-w.size()+1],w[j]);
for(unsigned int j=0; j<w.size()-i; ++j)
c+=get_cost(v[j+1],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;
for(int j=start, cnt=0; cnt<N; j=(j+1)%N, ++cnt)
{
if(!cnt || value[ind[j]]!=value[ind[(j-1+N)%N]])
{
cost+=mincost(v,w);
v.clear();
w.clear();
}
if(value[ind[j]]!=value[j])
{
v.push_back(ind[j]);
w.push_back(j);
}
}
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;
}
printf("%d\n",CMIN);
return 0;
}