pku2628.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 78 行

#include <stdio.h>
#include <algorithm>
using namespace std;

typedef struct 
{
	int l, id;
} Node;

Node nd[60];
int ID[30];
int N;

bool cp(Node a, Node b)
{
	return a.l >= b.l;
}

bool Test(int l)
{
	int i;
	sort(ID, ID + l);
	for (i = 0; i < l - 1; i++)
	{
		if ((ID[i + 1] - ID[i]) * 2 >= N)
		{
			return 0;
		}
	}
	if (2 * (ID[0] - ID[l - 1] + N) >= N)
	{
		return 0;
	}
	return 1;
}

void Solve()
{
	int i, j, ans;
	for (i = 0; i < N; i++)
	{
		scanf("%d", &nd[i].l);
		nd[i].id = i;
	}
	sort(nd, nd + N, cp);
	ID[0] = nd[0].id;
	ID[1] = nd[1].id;
	ID[2] = nd[2].id;
	for (i = 3; i < N; i++)
	{
		if (Test(i))
		{
			for (j = 0, ans = 0; j < i; j++)
			{
				ans += nd[j].l - nd[i - 1].l;
			}
			printf("%d\n\n", ans);
			return;
		}
		ID[i] = nd[i].id;
	}
	for (j = 0, ans = 0; j < N; j++)
	{
		ans += nd[j].l - nd[N - 1].l;
	}
	printf("%d\n\n", ans);
}

int main()
{
	while (scanf("%d", &N) != -1 && N)
	{
		Solve();
	}
	return 0;
}