贪心算法----最小差距

2年前 (2022) 程序员胖胖胖虎阿

451 0 0

题目描述

　　
给定一些不同的一位数字，你可以从这些数字中选择若干个，并将它们按一定顺序排列，组成一个整数，把剩下的数字按一定顺序排列，组成另一个整数。组成的整数不能以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个数据的答案。即最小的差的绝对值。

样例输入

2
6
0 1 2 4 6 7
4
1 6 3 4

样例输出

28
5

`解决方案`

【思路】如果采用暴力穷举的方法，如果将N个数分为两组，两组中数字个数的差不超过1，这种情况下，时间复杂度为Cn n/2*(n/2)!*(n/2)!，时间复杂度比较大。

在此将问题分为几类：

（1） n=2：直接判断；

（2） n为奇数：将数字序列进行升序排序后，分别从头或者尾开始分配元素，将头元素分给第一组，将尾元素分给第二组，继而将下面的头元素分给第一组，下面的尾元素分给第二组....直到元素分配结束。

（3）n为偶数：枚举非零数字a[i]作为x的最高位，a[i+1]作为y的最高位，从右往左取k-1位加入x，从左往右取k-1位加入y，打擂台更新答案。（打擂台的意思即为，先选取一个擂主，继而挑战者上台挑战擂主，挑战成功便成为擂主，否则擂主守擂成功，然后下一个挑战者上台。。）

代码：

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 int a[15];
 5 int n;
 6 int abs(int x){ return (x<0?-x:x); }
 7 int work1(){
 8     if (a[1]==0) swap(a[1],a[2]);
 9     int s1=0,s2=0;
10     for (int i=1;i<=n/2+1;i++) s1=s1*10+a[i];
11     for (int i=n;i>=n/2+2;i--) s2=s2*10+a[i];
12     return abs(s1-s2);
13 }
14 int work2(){
15     int book[15];//标志元素是否被使用过，使用过其值为1，否则为0
16     int s1,s2;
17     int ans=(1<<31)-1;
18     for (int i=2;i<=n;i++)
19         if (a[i-1]){
20             s1=a[i],s2=a[i-1];
21             memset(book,0,sizeof(book));
22             book[i]=book[i-1]=1;
23             int l=1,r=n;
24             for (int j=1;j<=(n-2)/2;j++){//每一轮选出俩个数字
25                 while (book[l]) l++;
26                 while (book[r]) r--;
27                 book[l]=book[r]=1;
28                 /*for(int i = 1;i<15;i++)
29                     printf("%d ",book[i]);*/
30                 s1=s1*10+a[l];s2=s2*10+a[r];
31             
32             }/*
33             printf("%d %d\n",s1, s2);*/
34             ans=min(ans,abs(s1-s2));
35       }
36     return ans;
37 }
38 int main(){
39     int t;
40     cin>>t;
41     while (t--){
42         scanf("%d",&n);
43         for (int i=1;i<=n;i++) scanf("%d",&a[i]);
44         sort(a+1,a+1+n);
45         if (n==2) { printf("%d\n",a[2]-a[1]);continue; }
46         if (n%2==1) printf("%d\n",work1()); else printf("%d\n",work2());
47     }
48 }