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,感兴趣的同学点波关注,我们尽快更新。