Pagini recente » Cod sursa (job #619339) | Cod sursa (job #2382561) | Cod sursa (job #103183) | Cod sursa (job #271232) | Cod sursa (job #1744460)
#include<fstream>
#include<algorithm>
#include<vector>
#include<cstring>
#define DIM 605
using namespace std;
int n, i, ii, nr, sum, sol, st, dr, mid, aux, nr1;
int v[DIM], w[DIM], f[DIM], r[DIM], u[DIM];
vector<int> poz[DIM];
ifstream fin("barman.in");
ofstream fout("barman.out");
int modul(int x){
if(x > 0){
return x;
}
return -x;
}
int main(){
fin>> n;
for(i = 1; i <= n; i++){
fin>> v[i];
w[i] = v[i];
}
sort(w + 1, w + n + 1);
nr = 1;
for(i = 2; i <= n; i++){
if(w[i] != w[nr]){
w[++nr] = w[i];
}
}
for(i = 1; i <= n; i++){
st = 1;
dr = nr;
while(st <= dr){
mid = (st + dr) / 2;
if(v[i] == w[mid]){
break;
}
else{
if(v[i] > w[mid]){
st = mid + 1;
}
else{
dr = mid - 1;
}
}
}
v[i] = mid;
f[mid]++;
}
for(i = 1; i <= nr; i++){
while(f[i] != 0){
r[++nr1] = i;
f[i]--;
}
}
sol = 1000000000;
for(ii = 1; ii < n; ii++){
sum = 0;
for(i = 1; i <= nr; i++){
poz[i].clear();
u[i] = 0;
}
memset(f, 0, sizeof(f));
for(i = 1; i <= n; i++){
if(v[i] == r[i]){
f[i] = 1;
}
else{
poz[ r[i] ].push_back(i);
}
}
for(i = 1; i <= n; i++){
if(f[i] == 0){
sum += 20;
sum += modul(i - poz[ v[i] ][ u[ v[i] ] ]);
u[ v[i] ]++;
}
}
sol = min(sol, sum);
aux = r[n];
for(i = n - 1; i >= 1; i--){
r[i + 1] = r[i];
}
r[1] = aux;
}
fout<< sol <<"\n";
return 0;
}