• 题目：Knowledge Test about Match

• 题意：给出n个数bi（ 范围是0 ~ (n-1)），这n个数与ai( 依次为0 ~ （n-1））进行匹配，使得

\[min{\sum_{i = 0}^{n-1}\sqrt{|b_{i} -a_{i}|}} \]

• 解析：此题允许存在一定的误差，所以可以通过贪心 + 暴力匹配的方式进行乱搞来降低误差率，首先我们肯定希望两个数之差尽可能的小，我们将bi从小到大进行排序，由于sqrt的导数是随着x增大而减小的，所以我们不能直接贪心进行匹配，这样误差较大，我们可以判断第i个数bi（代码里的ai）与i匹配的结果 + bj与j匹配的结果 和 bi与j匹配的结果 + bj与i匹配的结果进行比较，若前者比后者大，说明bj更适合与i匹配，所以我们采用贪心策略交换一下bi与bj达到局部最优。
• 升华：此处的贪心算法可能实现了局部最优但最后并不是全局最优，我们可以通过多次实现局部最优降低结果误差。
• 代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 1005;
int a[N];
int n, T;
double cal(int x, int y)
{
    return sqrt(abs(x - y));
}
int main()
{
    scanf("%d", &T);
    while(T --)
    {
        scanf("%d", &n);
        for(int i = 0; i < n ; i++) scanf("%d", &a[i]);
        sort(a, a + n);
        int times = 2; // 重复进行匹配, 降低误差率，可能完成一次匹配后第二次能匹配到更优的结果
        while(times --)
        {
            for(int i = 0; i < n; i++)
            {
                for(int j = i + 1; j < n; j++)
                {
                    if(cal(i, a[i]) + cal(j, a[j]) > cal(i, a[j]) + cal(j, a[i]) )
                        swap(a[i], a[j]);
                }
            }
        }
        for(int i = 0; i < n; i++)
            printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');
    }
}