Pagini recente » Cod sursa (job #88031) | Cod sursa (job #72613) | Cod sursa (job #118420) | Cod sursa (job #169929) | Cod sursa (job #2040683)
#include <fstream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
#define x first
#define y second
#define ll long long
#define MAXN 600
ifstream fin("barman.in");
ofstream fout("barman.out");
bool viz[MAXN + 1], ok[MAXN + 1];
int v[MAXN + 1], c[MAXN + 1], start[MAXN + 1], sef;
vector <int> g[MAXN + 1];
pair <int, int> a[MAXN + 1];
inline bool interior(int l, int r, int x) {
if (l <= r) return (l <= x && x <= r);
else return (x <= r || x >= l);
}
inline ll calc(int n, int k) {
int l = start[k], r = start[k % sef + 1] - 1;
if (r == 0) r = n;
ll sum = 0;
for (int i = 0; i < (int)g[k].size(); i++)
if (interior(l, r, g[k][i])) ok[i] = 1, viz[g[k][i]] = 1;
else ok[i] = 0;
if (l <= r) {
int p = l;
for (int i = 0; i < (int)g[k].size(); i++) if (ok[i] == 0) {
while (viz[p]) p++;
sum += abs(g[k][i] - p) + 20;
p++;
}
} else {
int p = 1;
for (int i = 0; i < (int)g[k].size(); i++) if (ok[i] == 0) {
if (p <= r) {
while (p <= r && viz[p]) p++;
if (p > r) p = l;
while (viz[p]) p++;
} else while (viz[p]) p++;
sum += abs(g[k][i] - p) + 20;
if (p == r) p = l;
else p++;
}
}
for (int i = 0; i < (int)g[k].size(); i++)
if (ok[i])
ok[i] = 0, viz[g[k][i]] = 0;
return sum;
}
int main() {
int n;
fin >> n;
for (int i = 1; i <= n; i++)
fin >> a[i].x, a[i].y = i;
sort(a + 1, a + n + 1);
int k = 0;
for (int i = 1; i <= n; i++)
if (a[i].x == a[i - 1].x) v[i] = k;
else v[i] = ++k;
for (int i = 1; i <= n; i++)
c[v[i]] = a[i].x;
for (int i = 1; i <= n; i++)
if (v[i] > v[i - 1])
start[v[i]] = i;
for (int i = 1; i <= n; i++)
g[v[i]].push_back(a[i].y);
for (int i = 1; i <= k; i++)
sort(g[i].begin(), g[i].end());
sef = k;
ll ans = -1;
for (int i = 0; i < n; i++) {
ll sum = 0;
for (int j = 1; j <= k; j++)
sum += calc(n, j);
if (ans == -1 || sum < ans)
ans = sum;
for (int j = 0; j < n; j++)
v[j] = v[j + 1];
v[n] = v[0];
for (int j = 1; j <= k; j++) {
start[j]--;
if (start[j] == 0)
start[j] = n;
}
}
fout << ans;
return 0;
}