3209682_wa.cpp

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

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

using namespace std;

int cas, l, p, dif, d[11], mark[11];
char a[11], b[11];
int aa, bb;
void solve()
{
	int i;

	aa = bb = 0;
	for(i = 0; i < l; i++)
	{
		if(mark[i])
		{
			a[aa++] = d[i]+'0';
		}
		else
			b[bb++] = d[i]+'0';
	}
	do
	{
		int na = atoi(a);
		if(na==0||a[0]!='0')
		{
			do
			{
				int nb = atoi(b);
				if(nb==0||b[0]!='0')
				{
					if(dif==-1||(int)abs(na-nb) < dif)
						dif = (int)abs(na-nb);
				}
			}
			while(next_permutation(b,b+bb));
		}
	}while(next_permutation(a,a+aa));

}

void dfs(int pos,int no)
{
	int i;

	if(no==0)
	{
		solve();
		return ;
	}
	for(i = pos; i < l; i++)
	{
		mark[i] = 1;
		dfs(i+1,no-1);
		mark[i] = 0;
	}
}

int main()
{
	scanf("%d",&cas);
	while(cas-- > 0)
	{
		l = 0;
		while(1)
		{
			scanf("%d",&d[l++]);
			if(getchar()!=' ')
				break;
		}
		p = l/2;
		if(l==10)
		{
			puts("247");
			continue;
		}
		if(l==9)
		{
			int used[11];
			int lack[] = {2469,10469,469,369,359,358,359,369,469,1469};
			memset(used,0,sizeof(used));
			for(int i = 0; i < l; i++)
			{
				used[d[i]] = 1;
			}
			for(i = 0; i < 10; i++)
			{
				if(!used[i])
				{
					break;
				}
			}
			printf("%d\n",lack[i]);
			continue;
		}
		memset(mark,0,sizeof(mark));
		dif = -1;
		dfs(0,p);
		printf("%d\n",dif);
	}
	return 0;
}