Pagini recente » Cod sursa (job #1471351) | Cod sursa (job #1788134) | Cod sursa (job #264915) | Cod sursa (job #203398) | Cod sursa (job #2642122)
#include <cstdio>
#include <algorithm>
#include <vector>
#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 abs(int x , int y)
{
if(x > y)
swap(x , y);
return min(y - x , x + n - y);
}
int main()
{
freopen("barman.in" , "r" , stdin);
freopen("barman.out" , "w" , stdout);
int i , j , k , cnt , minim , sum;
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 = 1 ; i <= cnt ; i ++)
sort(T1[i].begin() , T1[i].end());
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 --;
}
for(k = 0 ; k < aux.size() ; k ++)
sum += abs(aux[k] - T2[j][k]) + 20;
}
minim = min(minim , sum);
}
printf("%d\n" , minim);
return 0;
}