算法-电子科技大学链时代工作室招新题C语言部分---题号D

1. 题目

这道题大概的意思就是对一个整形数组的元素进行排序，然后按新的顺序打印原本的下标；

例如，在题目给出的Note部分，{a1, a2, a3, a4, a5}进行排序之后变为了{a2, a1, a4, a3, a5}，于是输出2 1 4 3 5。

排序的规则是，排完序之后，使得新数组与原数组的每个对应位置上的元素相加之后，的到一个相同的数；

例如，在题目给出的Note部分，a1 + a2 = 6，a2 + a3 = 6，……

输入

第一行输入数组的元素个数，第二行输入数组的内容

输出

依次输出新数组的原下标，如果无法找到这样一个新的排列顺序，就输出-1。

2. 第一版解法

第一版是暴力解法，直接对题意进行翻译，结果也是不出意外地超时了。

2.1 思路

1. 首先假设第一个元素与第i个元素配对，并将它们的和存在一个变量sum中。

2. 然后依次检查之后的元素是否能找到另一个元素与其相加，得到的和恰好等于sum。

3. 如果某个元素找不到与其相对应的元素，就使第一个元素与i+1个元素配对，并重新检查。

4. 若检查到最后，每一个元素都无法和第一个元素配对，则表示无法找到符合题意的排序，打印-1并退出。

5. 如果第一个元素与某个元素配对时，每一个元素都能找到与自己相配对的元素，则按顺序打印与原数组相配对的元素的下标。

2.2 代码

#include <stdio.h>
#include <stdlib.h>

void sort(int n, int arr[])
{
    int i = 0;
    for(i = 0; i < n; i++)//arr[0]和arr[i]对应
    {
        int x = 1;
        int* ret = (int*)malloc(sizeof(int) * n);
        int* test = (int*)malloc(sizeof(int) * n);
        for(int h = 0; h < n; h++)
        {
            test[h] = 1;
        }
        ret[0] = i;
        test[i] = 0;
        int tmp = arr[0] + arr[i];
        int j = 1;
        for(j = 1; j < n; j++)//后面元素找对应
        {
            int flag = 1;
            for(int k = 0; k < n; k++)
            {
                if((tmp == arr[j] + arr[k])&&test[k] != 0)//找到对应元素
                {
                    flag = 0;
                    test[k] = 0;
                    ret[x] = k;
                    x++;
                    break;
                }
            }
            if(flag)//某号元素找不到对应
            break;
        }
        if(j == n)//找全了
        {
            for(int y = 0; y < n; y++)
            {
                printf("%d ", ret[y]+1);
            }
            break;
        }
        free(ret);
        free(test);
    }
    if(i == n)
    printf("-1\n");
}

int main()
{
    int n = 0, k = 0;
    k = scanf("%d", &n);
    int* arr = (int*)malloc(sizeof(int) * n);
    for(int i = 0; i < n; i++)
    {
        k = scanf("%d", &arr[i]);
    }
    sort(n, arr);
    free(arr);
    return 0;
}

2.3 总结

这一版解法缺乏对题目的深入分析，以及对数学关系的挖掘。

由此导致程序做了很多不必要的计算，使得时间复杂度过高而超时。

3. 第二版解法

这一版尝试减小时间复杂度。

3.1 挖掘数学关系，优化算法

3.1.1 有关sum

1. sum是每组元素相加之和，我们仔细分析就会发现，sum其实是平均数的二倍，于是我们无需再尝试第一个元素该与谁配对。

2. 其次，sum是两个整形之和，它也必定为整数，所以我们将sum定义为浮点数，并检验“sum == (int)sum”是否成立，如果不成立则直接输出-1。这样，某些不能找到结果的样例就可以直接判断为不符合要求，而不需要找到最后再做出判断；

例如数组{1, 2, 3, 7}，其平均数的二倍为6.5，一定不能找到合适的结果。

3.1.2 有关配对

如果第1号元素与第5号元素配对了，那么我们就不必再去寻找第5号元素该与第几号元素配对，直接使其与1号元素配对即可；

例如题上第一个案例{4, 2, 5, 1, 3}，打印的结果为2 1 4 3 5

结果的第一个位置上是2，第二个位置上是1

           第三个位置上是4，第四个位置上是3

           第五个位置上是5。

这样就可以为我们的循环减少一半的工作量。

3.2 代码

#include <stdio.h>
#include <stdlib.h>

void solve(int n, int arr[])
{
    double sum = 0;
    for(int j = 0; j < n; j++)
    {
        sum += (double)arr[j];
    }
    sum = sum*2/n;
    if(sum == (int)sum)
    {
        int i = 0;
        int ret[n];
        for(int j = 0; j < n; j++)
        {
            ret[j] = 0;
        }
        for(i = 0; i < n; i++)
        {
            if(ret[i] != 0)
            continue;
            int flag = 1;
            for(int j = 0; j < n; j++)
            {
                if(ret[j] != 0)
                continue;
                if(arr[i] + arr[j] == sum)
                {
                    flag = 0;
                    ret[i] = j + 1;
                    ret[j] = i + 1;
                    break;
                }
            }
            if(flag)
            {
                printf("%d\n", -1);
                return;
            }
        }
        if(i == n)
        for(int k = 0; k < n; k++)
        printf("%d ", ret[k]);
        printf("\n");
    }
    else
    printf("%d\n", -1);
}

int main()
{
    int n = 0, k = 0;
    k = scanf("%d", &n);
    int* arr = (int*)malloc(sizeof(int) * n);
    for(int i = 0; i < n; i++)
    {
        k = scanf("%d", &arr[i]);
    }
    solve(n, arr);
    free(arr);
    return 0;
}

3.3 总结

这次深入分析了题目中的数学关系，并对算法做了大量的优化。

但是仍然超时，能反应的过来吗牢底？我当时血压都高了。

但是没办法，我们只能继续做优化。

4. 最终版本

算法已经够简单了，优化一下思路。

4.1 换个思路

就刚才的思路而言，我们必须要用到二重循环，尽管我们已经将二重循环的工作量减少了一半，但仍然超时。那么就说明，一定有更好的算法，使得时间复杂度能降到O(n)

4.1.1 排序的思路

经过上一版的启发，我们发现，最大的数一定和最小的数配对，第二小的数一定和第二大的数配对……

于是，我们想到先将数组进行排序，这样就不必再费力再用二重循环去找配对的元素了。

可是，有两个问题（这也是我一开始没有采用这种思路的原因）：

1. 排序的实现，仍然需要二重循环（博主比较菜，还只会冒泡排序）。

2. 排序之后如何知道每个元素原来的下标。

对于第一个问题，我们可以只用qsort函数来帮助我们实现排序，因为其采用的是一种快速排序的方法。

对于第二个问题：

1. 我一开始的想法是将原数组的数据存储到一个结构体数组中，结构体包含两个元素，一个是int类型的数据，一个是该数据对应的下标。让qsort函数按照数据排序，我再访问另一个成员对下标进行配对。

2. 但是，数据本来就是由两部分构成的啊：数据的值与地址。所以我可以将各个元素的地址存放到一个指针数组中，然后让qsort根据其指向的值对地址进行排序，又由地址减去arr的到下标，进行配对。

4.2 代码

#include <stdio.h>
#include <stdlib.h>

int add_cmp(const void* e1, const void* e2)
{
    return **(int**)e1 - **(int**)e2;
}

void solve(int n, int arr[])
{
    double sum = 0;
    for(int j = 0; j < n; j++)
    {
        sum += (double)arr[j];
    }
    sum = sum*2/n;
    if(sum == (int)sum)
    {
        int** add = (int**)malloc(sizeof(int*) * n);
        int* ret = (int*)malloc(sizeof(int) * n);
        for(int i = 0; i < n; i++)
        {
            add[i] = &arr[i];
        }
        qsort(add, n, sizeof(int*), add_cmp);
        for(int i = 0, j = n-1; i <= j; i++, j--)
        {
            if(*add[i] + *add[j] != sum)
            {
                printf("%d\n", -1);
                return;
            }
            else
            {
                int e1 = add[i] - arr;
                int e2 = add[j] - arr;
                ret[e1] = e2 + 1;
                ret[e2] = e1 + 1;
            }
        }
        for(int i = 0; i < n; i++)
        {
            printf("%d ", ret[i]);
        }
        printf("\n");
        free(add);
        free(ret);
    }
    else
    printf("%d\n", -1);
}

int main()
{
    int n = 0, k = 0;
    k = scanf("%d", &n);
    int* arr = (int*)malloc(sizeof(int) * n);
    for(int i = 0; i < n; i++)
    {
        k = scanf("%d", &arr[i]);
    }
    solve(n, arr);
    free(arr);
    return 0;
}

4.3 总结

这次循环最多只有一重了，如果再不过就不太厚道了。那么也是理所当然地拿下第一题。

你问为什么第一题是D？因为前三道是保护自尊心的送分题，小学生都会做，我们就直接跳过。

C语言题的题号一直到H，感兴趣的同学点波关注，我们尽快更新。