Pagini recente » Cod sursa (job #2181923) | Cod sursa (job #347172) | Cod sursa (job #1956316) | Cod sursa (job #2658685) | Cod sursa (job #347393)
Cod sursa(job #347393)
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
#define MAX_N 610
#define inf 2147000000
int n, add, sol, val;
int A[MAX_N], B[MAX_N], nr[MAX_N], loc[MAX_N];
int poz[MAX_N], el[MAX_N];
void cit() {
freopen("barman.in", "r", stdin);
freopen("barman.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &A[i]);
B[i] = A[i]; loc[i] = i;
}
sort(B + 1, B + n + 1);
}
void perm() {
int aux = A[1];
for (int i = 1; i < n; i++)
A[i] = A[i + 1];
A[n] = aux;
aux = loc[1];
for (int i = 1; i < n; i++)
loc[i] = loc[i + 1];
loc[n] = aux;
}
void solve() {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (A[j] == B[i])
nr[i]++;
sol = inf;
for (int k = 1; k <= n; k++) {
int last = 1;
val = 0;
for (int i = 1; i <= n; i++)
if (B[i] != B[i - 1]) {
//voi pune cele nr[t] elemente pe pozitiile last..last + nr[i] - 1
poz[0] = el[0] = 0;
for (int j = last; j <= last + nr[i] - 1; j++)
if (A[j] != B[i])
poz[++poz[0]] = j;
for (int j = 1; j <= n; j++)
if (A[j] == B[i] && (j < last || last + nr[i] - 1 < j))
el[++el[0]] = j;
add = 0;
for (int j = 1; j <= el[0]; j++)
add += abs(loc[el[j]] - loc[poz[j]]);
val += add;
last = last + nr[i];
}
if (val < sol) sol = val;
perm();
}
printf("%d\n", sol);
}
int main() {
cit();
solve();
return 0;
}