两两配对差值最小

题解：

题目难度：二星

考察点： 贪心，排序，哈希

解法一：贪心+排序

将一个数列中的所有数两两配对并求和，在这些和中选出最大和最小值，使得二者差距最小。很显然就是要让所有的配对的和的大小尽量相等，试想一下，如果让大的和大的配对，小的和小的配对，那么最大值和最小值的差距将会进一步拉大，因此一种可行的贪心思路就是让大的尽量和小的配对，这样最大值和最小值的差距可以缩小，“和”的分布也会尽量平均。因此就会有如下解法，首先将数组从小打大进行排序，然后我们让第一个和最后一个配对，第二个和倒数第二个配对，如此下去。在配对的同时维护这些配对和的最小值和最大值，最后用最大值减去最小值就是所求，复杂度为

#include "bits/stdc++.h"
using namespace std;
const int maxn=10000+1;
int n,a[maxn];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    int i=1,j=n;
    int mx=INT_MIN,mi=INT_MAX;
    while(i<j){
        mx=max(mx,a[i]+a[j]);
        mi=min(mi,a[i]+a[j]);
        i++,j--;
    }
    printf("%d\n",mx-mi);    
    return 0;
}

解法二：哈希表

题目中明确说明数组中每个数不超过，因此可以很容易通过哈希表将整个数组映射到的空间内，并统计出每个值出现的次数。然后设置两个指针，指向，指向，从前往后移动，从后往前移动。同时设置和表示配对和的最小值和最大值。当或指向的值出现次数为时，移动对应的指针，否则，将作为一组新的配对和，去分别更新和，并对和分别减去二者出现次数的最小值。最后用就是所求。其实思路和解法一是大致相同的，主体思想都是大小配对贪心，只是方法一对数据进行了排序，而方法二映射到了的空间内，复杂度为

#include "bits/stdc++.h"
using namespace std;
const int maxn=10000+1;
int n,a[maxn],vis[maxn];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        vis[a[i]]++;
    }
    int i=0,j=100,mi=INT_MAX,mx=INT_MIN;
    while(i<=j){
        if(!vis[i]){
            i++;
            continue;
        }
        if(!vis[j]){
            j--;
            continue;
        }
        int num=min(vis[i],vis[j]);
        vis[i]-=num;
        if(i<j) vis[j]-=num;
        mi=min(mi,i+j);
        mx=max(mx,i+j);
    }
    printf("%d\n",mx-mi);    
    return 0;
}