pku2576.cpp

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

#include <stdio.h>
#include <stdlib.h>

int we[110], max, sum;

int abs(int a)
{
	if (a > 0)
	{
		return a;
	}
	else
	{
		return -a;
	}
}

int main()
{
	int N, i, s1, s2, p1, p2, tmp, l1, l2, min;
	while (scanf("%d", &N) != -1 && N != 0)
	{
		for (i = 0; i < N; i++)
		{
			scanf("%d", &we[i]);
		}

		l1 = N / 2;
		l2 = N - l1;

		for (i = 0, s1 = 0; i < l1; i++)
		{
			s1 += we[i];
		}
		for (i = 0, s2 = 0; i < l2; i++)
		{
			s2 += we[l1 + i];
		}
		
		min = abs(s2 - s1);

		for (i = 0; i < 100; i++)
		{
			p1 = rand() % l1;
			p2 = rand() % l2 + l1;
			
			tmp = abs(s1 - s2 - we[p1] * 2 + we[p2] * 2);

			if (tmp < min)
			{
				min = tmp;
				s1 = s1 - we[p1] + we[p2];
				s2 = s2 - we[p2] + we[p1];
				tmp = we[p1];
				we[p1] = we[p2];
				we[p2] = tmp;
			}
		}
		if (s1 > s2)
		{
			printf("%d %d\n", s2, s1);
		}
		else
		{
			printf("%d %d\n", s1, s2);
		}
	}
}