Pagini recente » Cod sursa (job #199300) | Cod sursa (job #712405) | Cod sursa (job #3130678) | Cod sursa (job #124475) | Cod sursa (job #2642121)
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define nod first
#define cost second
using namespace std;
const int NMAX = 600;
const int INF = 2.e9;
typedef pair <int , int> muchii;
vector <int> T1[NMAX + 5];
int v[NMAX + 5] , n;
muchii s[2 * NMAX + 5];
int cmp(muchii a , muchii b)
{
return a.cost < b.cost;
}
int main()
{
freopen("barman.in" , "r" , stdin);
freopen("barman.out" , "w" , stdout);
int i , j , k , cnt , minim , sum , l;
scanf("%d" , &n);
for(i = 0 ; i < n ; i ++)
{
scanf("%d" , &v[i]);
s[i] = {i , v[i]};
}
sort(s , s + n , cmp);
cnt = 1;
for(i = 0 ; i < n ; i ++)
{
if(i > 0 && s[i].cost != s[i - 1].cost)
cnt ++;
v[s[i].nod] = cnt;
T1[cnt].push_back(s[i].nod);
}
for(i = n ; i < 2 * n ; i ++)
{
s[i].cost = v[s[i - n].nod];
s[i - n].cost = v[s[i - n].nod];
}
minim = INF;
for(i = 0 ; i < n ; i ++)
{
vector <int> T2[NMAX + 5];
for(j = i ; j < n + i ; j ++)
T2[s[j].cost].push_back(j - i);
sum = 0;
for(j = 1 ; j <= cnt ; j ++)
{
vector <int> aux;
for(k = 0 ; k < T1[j].size() ; k ++)
aux.push_back(T1[j][k]);
for(k = 0 ; k < aux.size() ; k ++)
if(aux[k] == T2[j][k])
{
aux.erase(aux.begin() + k);
T2[j].erase(T2[j].begin() + k);
k --;
}
int f[NMAX + 5];
memset(f , 0 , sizeof(f));
for(k = 0 ; k < T2[j].size() ; k ++)
f[T2[j][k]] = 1;
for(k = 0 ; k < aux.size() ; k ++)
for(l = 0 ; l < n ; l ++)
if(f[l])
{
sum += abs(aux[k] - l) + 20;
f[l] = 0;
break;
}
}
minim = min(minim , sum);
}
printf("%d\n" , minim);
return 0;
}