Cod sursa(job #1746977)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 24 august 2016 12:04:55
Problema Barman Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define MAXN 650

using namespace std;

int n, a[MAXN];
int goal[MAXN], ind[MAXN], viz[MAXN];
vector<int> pos[MAXN];


bool cmp(int x, int y)
{
	if (a[x] != a[y]) return a[x] < a[y];
	return x < y;
}

void normalizare()
{
	int fi[MAXN];
	for (int i = 1; i <= n; i++)
		goal[i] = i;
    sort(goal+1, goal+1+n, cmp);
    int nr = 1;
    for (int i = 1; i <= n; i++, nr++) {
		while (i < n && a[goal[i]] == a[goal[i+1]])
            fi[goal[i++]] = nr;
		fi[goal[i]] = nr;
    }
    for (int i = 1; i <= n; i++)
		a[i] = fi[i];
	//for (int i = 1; i <= n; i++)
		//printf("%d ", a[i]);
}

int dist(int i, int j)
{
    return max(i-j, j-i);
}

int cupleaza()
{
	int toR = 0;
    for (int i = 1; i <= n; i++) pos[i].clear(), ind[i] = 0;
    for (int i = 1; i <= n; i++)
		if (a[i] != goal[i])
			pos[goal[i]].push_back(i);
	for (int i = 1; i <= n; i++)
		if (a[i] != goal[i]) {
			toR += 20 + dist(i, pos[a[i]][ind[a[i]]]);
            ind[a[i]]++;
		}
	return toR;
}

void solve()
{
	for (int i = 1; i <= n; i++)
		goal[i] = a[i];
	sort(goal+1, goal+n+1);
    int best = cupleaza();
    for (int i = 0; i < n; i++) {
        for (int i = 1; i <= n-1; i++)
            swap(goal[i], goal[i+1]);
		best = min(best, cupleaza());
    }
    printf("%d", best);
}

int main()
{
	freopen("barman.in", "r", stdin);
	freopen("barman.out", "w", stdout);

    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	normalizare();
    solve();

    return 0;
}