1148.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

///////////////////////////////////////////////////////
//Utopia Divided
//
//
//

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

int num[20000], n;
int ans_x[10000], ans_y[10000],sign_x[10000], sign_y[10000];
const int xsign[]={ 1, -1, -1, 1 },ysign[]={ 1, 1, -1, -1}, h[]={ 1, -1};

void creat(int end, int num[], int sign[], int ans[], int last_sign)
{
	if( end == 0 )
	{
		ans[0] = num[0]*last_sign;
		return ;
	}

	if( last_sign == sign[end-1])
	{
		ans[end]=num[0]*last_sign*h[end%2];
		creat(end-1,num+1,sign,ans,last_sign);
	}
	else
	{
		ans[end] = num[end]*last_sign;
		creat(end-1,num,sign,ans,-last_sign);
	}
	return ;
}


int main()
{
	int i, j, t;
	scanf( "%d", &n );
	for(i=0;i<2*n;i++)
		scanf("%d",&num[i]);
	
	for(i=0;i<n;i++)
	{
		scanf("%d",&t);
		sign_x[i]=xsign[t-1];
		sign_y[i]=ysign[t-1];
	}

	std::sort(num,num+2*n);

	creat(n-1,num,sign_x,ans_x,sign_x[n-1]);
	creat(n-1,num+n,sign_y,ans_y,sign_y[n-1]);

	for(i=0;i<n;i++)
	{
		if(ans_x[i]>0)printf("+");
		printf("%d ",ans_x[i]);
		if(ans_y[i]>0)printf("+");
		printf("%d\n",ans_y[i]);
	}

	return 0;
}