poj2718 Smallest Difference(穷竭搜索之next_permutation)

题意

给你几个位，用这些位凑成两个数，

问这两个数的差的绝对值最小是多少。

心得

n<=10，n!=362W也可以做，

直接就用o(n!)的做法就好啦，穷举。

值得注意的几个地方：

①没说明位的个数，用字符串即读入挂处理。

②用位数剪枝，显然一个是n/2位，一个是n-n/2位，

   即二者最多相差1位。

③前导0的处理，纯0不是前导0。

代码

#include <iostream>
#include <algorithm> 
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <functional>
const int INF=0x3f3f3f3f;
const int maxn=1e5+10; 
const int mod=1e9+7;
const int MOD=998244353;
const double eps=1e-7;
typedef long long ll;
#define vi vector<int> 
#define si set<int>
#define pii pair<int,int> 
#define pi acos(-1.0)
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define sci(x) scanf("%d",&(x))
#define scll(x) scanf("%lld",&(x))
#define sclf(x) scanf("%lf",&(x))
#define pri(x) printf("%d",(x))
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define mem(a,b) memset(a,b,sizeof(a)) 
using namespace std;
int t,b[15],ans;
bool flag[15];
char p[35];
int main()
{ 
  sci(t);
  getchar();
  while(t--)
  {
  	gets(p);mem(flag,0);mem(b,0);
	ans=INF;
  	int cnt=0;
  	int len=strlen(p);
  	rep(i,0,len-1)
  	{
  		if(p[i]>='0'&&p[i]<='9')
  		{
  		 int t=p[i]-'0';
  		 flag[t]=1;
  	    }
  	}
  	rep(i,0,9)if(flag[i])b[cnt++]=i;
  	do
  	{
  		int l,r,lpos,rpos;
  		int i=max(0,cnt/2-1);//i为l最后一位  
  		{
  			l=0,r=0;
			lpos=0,rpos=i+1;
  			if(b[lpos]==0&&i-lpos)continue;//有非0的前导0 
			if(b[rpos]==0&&cnt-1-rpos)continue;
  			while(lpos<=i)l=10*l+b[lpos++];
  			while(rpos<=cnt-1)r=10*r+b[rpos++];
  			ans=min(ans,abs(r-l));
  		}
  	}while(next_permutation(b,b+cnt));
  	printf("%d\n",ans);
  }
  return 0;
}