2846087_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
//#include <time.h>
#include <algorithm>

using namespace std;

int a[101];
int n;
int n1[101], n2[101];
int c, d;

int main()
{
	int i, t, inf;
	int ta, tb, tmp;
	int sum1, sum2;
	int min, max;
	int ansb, anss;



//	srand((unsigned)time(NULL) );
	scanf("%d",&n);
	for(i = 1; i <= n; i++)
		scanf("%d",&a[i]);
	sort(&a[1],&a[1]+n);
	t = 30;
	inf = 2100000000;
	while(t--)
	{	
		c = d = 0;
		i = 1;
		sum1 = sum2 = 0;
		if(n%2)
		{
			n1[0] = a[1];
			sum1 = a[1];
			d = 1;
			i = 2;
		}
		for(; i < n; i+=2)
		{
			n2[c++] = a[i];
			sum2 += a[i];
			n1[d++] =  a[i+1];
			sum1 += a[i+1];
			ta = (rand()%c+c)%c;
			tb = (rand()%d+d)%d;
			sum2 -= n2[ta];sum2 += n1[tb];
			sum1 -= n1[tb];sum1 += n2[ta];
			tmp = n2[ta];
			n2[ta] = n1[tb];
			n1[tb] = tmp;
		}
		max = sum1>sum2?sum1:sum2;
		min = sum1<sum2?sum1:sum2;
		if(max-min<inf)
		{
			inf = max-min;
			ansb = max;
			anss = min;
		}
	}
	printf("%d %d\n",anss,ansb);
	return 0;
}