给定一些不同的一位数字，你可以从这些数字中选择若干个，并将它们按一定顺序排列，组成一个整数，把剩下的数字按一定顺序排列，组成另一个整数。组成的整数不能以0开头（除非这个整数只有1位）。 例如，给定6个数字，0,1,2,4,6,7，你可以用它们组成一对数10和2467，当然，还可以组成其他的很多对数，比如210和764，204和176。这些对数中两个数差的绝对值最小的是204和176，为28。 给定N个不同的0~9之间的数字，请你求出用这些数字组成的每对数中，差的绝对值最小的一对（或多对）数的绝对值是多少？
第一行包括一个数T（T≤1000），为测试数据的组数。 每组数据包括两行，第一行为一个数N（2≤N≤10），表示数字的个数。下面一行为N个不同的一位数字。
T行，每行一个数，表示第i个数据的答案。即最小的差的绝对值。
贪心，分奇数偶数讨论：
如果总数是奇数，排序过后正着（从第一个非零数开始）取(n/2)+1个，剩下的倒着取 如果总数是偶数， 从左到右选相邻两个差值最小的，然后首位小的那个倒着取，首位大的那个正着取 #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; int t,n,a[20],x[20],y[20],px=0,py=0,cnt[20],te=0; bool vis[20]; int suan(){ int A=0,B=0; if(n%2==0){ int sub=20, pos; for(int i=1;i<=n-1;i++) if(a[i+1]-a[i]<sub && a[i]!=0){ pos=i; sub=a[i+1]-a[i]; } vis[pos]=1;vis[pos+1]=1; x[++px]=a[pos]; y[++py]=a[pos+1]; for(int i=1;i<=(n/2)-1;){ for(int j=n;j>=1;j--){ if(!vis[j]){ x[++px]=a[j]; vis[j]=1; i++; if(i>=(n/2)-1) break; } } } for(int i=1;i<=n;i++){ if(!vis[i]){ y[++py]=a[i]; vis[i]=1; if(py>=(n/2)) break; } } }else{ for(int i=1;i<=n;i++){ if(a[i]!=0){ x[++px]=a[i]; vis[i]=1; break; } } for(int i=1;i<=n;i++){ if(!vis[i]){ x[++px]=a[i]; vis[i]=1; if(px>=(n/2)+1) break; } } for(int i=n;i>=1;i--){ if(!vis[i]){ y[++py]=a[i]; if(py>=(n/2)) break; } } } for(int i=1;i<=px;i++) A=A*10+x[i]; for(int i=1;i<=py;i++) B=B*10+y[i]; return abs(A-B); } int main(){ freopen("in.txt","r",stdin); scanf("%d",&t); memset(cnt,0,sizeof(cnt)); while(t--){ scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); vis[i]=0; cnt[a[i]]++; } memset(a,0x3f,sizeof(a)); for(int i=0;i<=9;i++) if(cnt[i]%2!=0) a[++te]=i; n=te; printf("%d\n",suan()); px=0; py=0; te=0; memset(cnt,0,sizeof(cnt)); } return 0; }转载于:https://www.cnblogs.com/leotan0321/p/6081389.html
相关资源：数据结构—成绩单生成器