Cod sursa(job #771549)

Utilizator darrenRares Buhai darren Data 26 iulie 2012 13:03:22
Problema Barman Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <cstring>
#include <fstream>
#include <algorithm>

using namespace std;

int N;
int A[602], B[602], C[602];
int fr[602], wh[602];
bool put[602], done[602];
int pos[602], result = 0x3f3f3f3f;

class compare
{
	public: inline bool operator () (const int& i1, const int& i2)
	{
		if (A[i1] != A[i2])
			return A[i1] < A[i2];
		return i1 < i2;
	}
};

inline int mabs(const int& x)
{
	return (x < 0 ? -x : x);
}
inline int real(const int& x, const int& y)
{
	return (x + y - 1 > N ? x + y - 1 - N : x + y - 1);
}

int main()
{
	ifstream fin("barman.in");
	ofstream fout("barman.out");
	
	fin >> N;
	for (int i = 1; i <= N; ++i)
	{
		fin >> A[i];
		pos[i] = i;
	}
	sort(pos + 1, pos + N + 1, compare());
	
	int now = 0;
	for (int i = 1; i <= N; ++i)
	{
		++now;
		while (i < N && A[pos[i]] == A[pos[i + 1]])
		{
			A[pos[i]] = now;
			++i;
		}
		A[pos[i]] = now;
	}
	
	for (int i = 1; i <= N; ++i)
		++fr[A[i]];
	for (int i = 1; i <= N; ++i)
		fr[i] += fr[i - 1];
	
	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= N; ++j)
			wh[j] = fr[j - 1] + 1;
		
		for (int j = i; j <= N; ++j)
			B[j - i + 1] = A[j];
		for (int j = 1; j < i; ++j)
			B[N - i + 1 + j] = A[j];
		
		memset(put, 0, sizeof(put));
		memset(done, 0, sizeof(done));
		for (int j = 1; j <= N; ++j)
			if (wh[B[j]] <= j && j < wh[B[j] + 1])
			{
				B[j] = j;
				put[j] = true;
				done[j] = true;
			}
		for (int j = 1; j <= N; ++j)
			if (!done[j])
			{
				while (put[wh[B[j]]])
					++wh[B[j]];
				B[j] = wh[B[j]];
			}
		
		int resultnow = 0;
		for (int j = 1; j <= N; ++j)
			if (B[j] != j)
			{
				resultnow += 20;
				resultnow += mabs(real(j, i) - real(B[j], i));
			}
		
		result = min(result, resultnow);
	}
	
	fout << result << '\n';
	
	fin.close();
	fout.close();
}