Pagini recente » Cod sursa (job #549825) | Cod sursa (job #1130639) | Cod sursa (job #514972) | Cod sursa (job #2492667) | Cod sursa (job #1327502)
#include <cmath>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#define MAXN 606
using namespace std;
struct pahar {
int val, pozs, pozd, pozi;
};
vector<pahar> v;
int N;
bool cmp(pahar x, pahar y) {
if(x.val == y.val)
return x.pozi < y.pozi;
return x.val < y.val;
}
vector<int> v1, v2;
bool viz[MAXN];
int solve() {
int ans = 0;
for(int i = 0; i < v1.size(); ++i)
viz[i] = 0;
for(int i = 0; i < v1.size(); ++i) {
int cur = i;
while(!viz[cur]) {
viz[cur] = 1;
ans += abs(v1[cur] - v2[cur]);
for(int j = 0; j < v1.size(); ++j) {
if(v1[j] == v2[cur]) {
cur = j;
break;
}
}
}
}
return ans;
}
int main()
{
//ifstream cin("barman.in");
//ofstream cout("barman.out");
int fin = 0;
long long cost = (1 << 30);
cin >> N;
for(int i = 1; i <= N; ++i) {
pahar p;
cin >> p.val;
p.pozi = p.pozs = p.pozd = i;
if(v.empty() || p.val != v[v.size() - 1]) {
v.push_back(p);
}
else {
++v[v.size() - 1].pozd;
}
}
sort(v.begin(), v.end(), cmp);
for(int i = 1; i <= N; ++i) {
long long ans = 0;
v1.clear();
v2.clear();
for(int j = 1; j <= N; ++j) {
int dec = (j + i - 1) % N;
if(!dec)
dec = N;
if(dec >= a[j].pozs && dec <= a[j].pozd) {
a[j + 1].pozs = dec + 1;
continue;
}
else {
ans += 20;
v1.push_back(a[j].pozi);
v2.push_back(dec);
}
}
ans += solve();
if(ans < cost) {
cost = ans;
fin = i;
}
}
cout << cost << '\n';
return 0;
}