Pagini recente » Cod sursa (job #2780750) | Cod sursa (job #2930953) | Cod sursa (job #48501) | Cod sursa (job #652474) | Cod sursa (job #526556)
Cod sursa(job #526556)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 610
int n;
int a[N],v[N],b[N];
int vrea[N][N];
int are[N][N];
int szVrea[N],szAre[N];
int rez = N*N*N;
inline void citire() {
scanf("%d",&n);
for(int i=1; i<=n; ++i) {
scanf("%d",&a[i]);
v[i] = a[i];
}
}
inline int caut(int x) {
if(v[1]==x)
return 1;
if(v[v[0]]==x)
return v[0];
int p=1,u=v[0],m;
while(p<u) {
m = (p+u)>>1;
if(x<=v[m])
u = m;
else
p = m+1;
}
return p;
}
inline void precalc() {
sort(v+1,v+n+1);
v[0] = 1;
for(int i=2; i<=n; ++i) {
if(v[v[0]]!=v[i])
v[++v[0]] = v[i];
}
for(int i=1; i<=n; ++i) {
a[i] = caut(a[i]);
b[i] = a[i];
}
sort(b+1,b+n+1);
}
inline int modul(int x) {
return ( (x<0) ? (-x) : (x) );
}
inline void rezolva() {
int n1 = n+1;
int rez1;
for(int i=1; i<=n; ++i) {
rez1 = 0;
memset(szVrea,0,sizeof(szVrea));
memset(szAre,0,sizeof(szAre));
for(int j=i,t=1; t<=n; ++t,++j) {
if(j==n1)
j = 1;
if(a[t]!=b[j]) {
++rez1;
are[a[t]][++szAre[a[t]]] = t;
vrea[b[j]][++szVrea[b[j]]] = t;
}
}
rez1 *= 20;
for(int j=1; j<=v[0]; ++j) {
for(int t=1; t<=szAre[j]; ++t)
rez1 += modul(vrea[j][t]-are[j][t]);
}
if(rez1<rez)
rez = rez1;
}
}
int main() {
freopen("barman.in","r",stdin);
freopen("barman.out","w",stdout);
citire();
precalc();
rezolva();
printf("%d\n",rez);
return 0;
}