Pagini recente » Cod sursa (job #2283410) | Cod sursa (job #31455) | Cod sursa (job #3262672) | Cod sursa (job #295810) | Cod sursa (job #2725054)
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const int N = 1202;
ifstream fin ("barman.in");
ofstream fout ("barman.out");
int n, v[N], v2[N], aux[N];
set<int>poz[N];
int main()
{
fin >> n;
for (int i = 1; i <= n; i++) {
fin >> v[i];
v2[i] = v[i];
}
sort(v2 + 1, v2 + n + 1);
for (int i = 1; i <= n; i++) {
v[i] = lower_bound(v2 + 1, v2 + n + 1, v[i]) - v2;
aux[i] = v2[i];
}
for (int i = 1; i <= n; i++)
v2[i] = lower_bound(aux + 1, aux + n + 1, v2[i]) - aux;
for (int i = 1; i <= n; i++)
v2[i + n] = v2[i];
int sol = INF;
for (int j = 1; j <= n; j++) {
poz[v[j]].insert(j);
}
for (int i = 1; i <= n; i++) {
int ans = 0, cnt = 0;
for (int j = 1; j <= n; j++)
if (v[j] == v2[i + j - 1])
poz[v[j]].erase(j);
for (int j = 1; j <= n; j++) {
if (v[j] != v2[j + i - 1]) {
auto x = poz[v2[i + j - 1]].lower_bound(j);
if (x == poz[v2[i + j - 1]].begin()) {
ans += abs(*x - j);
poz[v2[i + j - 1]].erase(x);
}
else {
x--;
ans += abs(*x - j);
poz[v2[i + j - 1]].erase(x);
}
cnt++;
}
}
for (int j = 1; j <= n; j++)
poz[v[j]].insert(j);
sol = min(sol, ans + 20 * cnt);
}
fout << sol;
return 0;
}