Pagini recente » Cod sursa (job #385321) | Cod sursa (job #2763690) | Cod sursa (job #634281) | Cod sursa (job #984217) | Cod sursa (job #1223142)
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
const int knmax = 605;
int n, gv[knmax], srt[knmax];
void get_positions(){
for(int i = 0; i < n; ++i)
srt[i] = gv[i];
sort(srt, srt + n);
int aux[knmax] = {0};
for(int i = 1; i < n; ++i)
if(srt[i] != srt[i - 1])
aux[i] = aux[i - 1] + 1;
else
aux[i] = aux[i - 1];
for(int i = 0; i < n; ++i){
int lef = 0, rai = n - 1, mid, val = gv[i];
while(lef <= rai){
mid = (lef + rai) / 2;
if(srt[mid] > val)
rai = mid - 1;
else if(srt[mid] < val)
lef = mid + 1;
else{
gv[i] = aux[mid];
break;
}
}
}
for(int i = 0; i < n; ++i)
srt[i] = gv[i];
sort(srt, srt + n);
}
int dist(int x, int y){
if(x < y)
return x + 1 + n - y;
return x - y;
}
int start(int s){
int ind = s, i = 0, rval = 0;
do{
int num = 1, x = srt[i], lt = i;
++i;
while(i < n && srt[i] == srt[i - 1]){
++i;
++num;
}
vector<int> oc;
for(int j = ind; j < i + ind - lt; ++j)
if(gv[j % n] != x)
oc.push_back(j % n);
vector<int> lef, rai;
int u = (i + ind - lt) % n;
while(u != ind){
if(gv[u] == x)
rai.push_back(u);
u = (u + 1) % n;
}
int p;
for(int j = 0; j < rai.size(); ++j)
rval += 20 + dist(rai[j], oc[j]);
p = rval;
while(!rai.empty()){
p -= dist(rai.back(), oc[lef.size()]);
lef.push_back(rai.back());
p += dist(oc[lef.size() - 1], lef.back());
rai.pop_back();
rval = min(rval, p);
}
ind = (ind + num) % n;
}while(ind != s);
return rval;
}
int main(){
ifstream in("barman.in");
ofstream out("barman.out");
in >> n;
for(int i = 0; i < n; ++i)
in >> gv[i];
get_positions();
int ans = 2e9;
for(int i = 0; i < n; ++i)
ans = min(ans, start(i));
out << ans;
return 0;
}