Pagini recente » Cod sursa (job #1709195) | Cod sursa (job #2415620) | Cod sursa (job #1286003) | Cod sursa (job #523737) | Cod sursa (job #771581)
Cod sursa(job #771581)
#include <cstring>
#include <fstream>
#include <algorithm>
#include <vector>
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;
vector<int> V[2][602];
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 <= fr[B[j]])
{
put[j] = true;
done[j] = true;
}
int resultnow = 0;
for (int j = 1; j <= N; ++j)
{
if (!done[j])
{
resultnow += 20;
V[0][B[j]].push_back(real(j, i));
}
for (int k = wh[j]; k <= fr[j]; ++k)
if (!put[k])
V[1][j].push_back(real(k, i));
}
for (int j = 1; j <= N; ++j)
{
sort(V[0][j].begin(), V[0][j].end());
sort(V[1][j].begin(), V[1][j].end());
while (!V[0][j].empty() && !V[1][j].empty())
{
resultnow += mabs(V[0][j].back() - V[1][j].back());
V[0][j].pop_back();
V[1][j].pop_back();
}
}
result = min(result, resultnow);
}
fout << result << '\n';
fin.close();
fout.close();
}