pku2549.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

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

typedef struct 
{
	int x, y, v;
}Node;

Node nd[size * size];
int num[size];
int N, cnt;

bool cp(Node a, Node b)
{
	return a.v < b.v;
}

void Input(int x)
{
	int i, j;
	for (i = 0; i < x; i++)
	{
		scanf("%d", &num[i]);
	}
	sort(num, num + x);
	cnt = 0;
	for (i = 0; i < x; i++)
	{
		for (j = i + 1; j < x; j++)
		{
			nd[cnt].x = i;
			nd[cnt].y = j;
			nd[cnt].v = num[i] + num[j];
			cnt++;
		}
	}
	sort(nd, nd + cnt, cp);
}

int search(int v)
{
	int f, l, m, p;
	f = 0;
	l = cnt - 1;
	while (f <= l)
	{
		m = (f + l) >> 1;
		if (nd[m].v == v)
		{
			for (p = m - 1; p >= 0; p--)
			{
				if (nd[p].v != v)
				{
					break;
				}
			}
			return p + 1;
		}
		else if (nd[m].v < v)
		{
			f = m + 1;
		}
		else
		{
			l = m - 1;
		}
	}
	return -1;
}

void Solve()
{
	int i, j, val, pos, q;
	for (i = N - 1; i >= 0; i--)
	{
		for (j = 0; j < N; j++)
		{
			if(i == j)
				continue;
			val = num[i] - num[j];
//			printf("val = %d\t", val);
			pos = search(val);
//			printf("pos = %d\n", pos);
			if (pos == -1)
			{
				continue;
			}
			else
			{
				for (q = pos; q < cnt && nd[q].v == val; q++)
				{
					if (nd[q].x != i && nd[q].x != j && nd[q].y != i && nd[q].y != j)
					{
						printf("%d\n", num[i]);
						return;
					}
				}
			}
		}
	}
	printf("no solution\n");
}

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