Pagini recente » Cod sursa (job #418573) | Cod sursa (job #2673975) | Cod sursa (job #2679811) | Cod sursa (job #2504085) | Cod sursa (job #1313574)
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
#include <deque>
#include <limits>
using namespace std;
int main()
{
ifstream cin("barman.in");
ofstream cout("barman.out");
int n;
cin >> n;
vector<int> v(n);
set<int> s;
for (int i = 0; i < n; i++) {
cin >> v[i];
s.insert(v[i]);
}
vector<int> sov(s.begin(), s.end());
vector<int> num(s.size(),0);
vector< vector<int> > who(num.size());
vector< pair<int, int> > a;
for (int i = 0; i < n; i++) {
v[i] = lower_bound(sov.begin(), sov.end(), v[i]) - sov.begin();
num[v[i]]++;
who[v[i]].push_back(i);
}
a.push_back({ 0, num[0] - 1 });
for (int i = 1; i < (int)num.size(); i++) {
num[i] += num[i - 1];
a.push_back({ num[i - 1], num[i] - 1 });
}
auto check = [&](const int& val,const int& j) {
if (a[val].first <= a[val].second) {
return (a[val].first <= j && j <= a[val].second);
}
return (j <= a[val].second || a[val].first <= j);
};
int ans = numeric_limits<int>::max();
for (int i = 0; i < n; i++) {
int ret = 0;
vector<bool> use(n,false);
vector< vector<int> > w(num.size());
for (int j = 0; j < n; j++) {
if (check(v[j], j) == false) {
w[v[j]].push_back(j);
} else {
use[j] = true;
}
}
for (int j = 0; j < (int)a.size(); j++) {
if (a[j].first <= a[j].second) {
for (int k = a[j].first, z = 0; k <= a[j].second; k++) {
if (!use[k]) {
ret += 20 + abs(k - w[j][z++]);
}
}
} else {
int z = 0;
for (int k = 0; k <= a[j].second; k++) {
if (!use[k]) {
ret += 20 + abs(k - w[j][z++]);
}
}
for (int k = a[j].first; k < n; k++) {
if (!use[k]) {
ret += 20 + abs(k - w[j][z++]);
}
}
}
}
for (int j = 0; j < (int)a.size(); j++) {
a[j].first++;
a[j].second++;
if (a[j].first == n) a[j].first = 0;
if (a[j].second == n) a[j].second = 0;
}
ans = min(ans, ret);
}
cout << ans;
return 0;
}