这个冒泡到底哪里有问题
新生入学后，图书馆将N
N 本书摆在一条书架上。书的编号为
1
,
2
,
…
,
N
1,2,…,N。
目前，这些书的顺序可能是乱的。管理员希望通过调整书的位置，使书架最终变为：第
1
1 个位置放编号
1
1 的书，第
2
2 个位置放编号
2
2 的书，依次类推。
书架前安装了一台轨道机械臂。每次操作时，小蓝可以选择三个连续的位置，机械臂会交换第一个位置和第三个位置上的书，中间位置上的书保持不动。
例如，当前书架顺序为
1
,
2
,
3
,
4
,
5
1,2,3,4,5。选择第
2
2 至第
4
4 个位置后，编号为
2
2 和
4
4 的书会交换，书架变为
1
,
4
,
3
,
2
,
5
1,4,3,2,5。
现在给出书架上
N
N 本书的当前顺序，请你计算，至少需要进行多少次操作，才能将书架恢复为
1
,
2
,
…
,
N
1,2,…,N 的顺序。如果无论如何都无法完成，输出
−
1
−1。
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
int n ;
scanf("%d",&n);
long long a;
for(int i = 0; i < n; i++)
{
scanf("%lld",&a);
if(a % 2 != (i + 1) % 2)
break;
printf("-1");
return 0;
}
long long ans = 0;
for(int j = 0; j < n - 2; j++)
{
for(int i = 0; i < n - 2; i++)
if(a > a)
{
long long t = a;
a = a;
a = t ;
ans++;
}
}
printf("%lld", ans);
return 0;
} 你的代码主要有这些问题：
[*] a 只是一个变量，没有数组，读入时每次都覆盖，后面无法比较和交换。
[*] 奇偶检查的 if 没有大括号，导致 printf("-1"); return 0; 无论条件如何都会执行，程序读第一个数就退出了。
[*] 冒泡里写的是 a > a，自己和自己比，永远不成立；而且交换的也是同一个变量，没有意义。
[*] 循环边界 n-2 不对，且没有对数组操作。
[*] 不能对整个数组直接冒泡排序。题目每次只能交换距离为 2 的两个位置，也就是只能交换奇数位置之间、偶数位置之间。直接冒泡会交换相邻的奇偶位置，这是不允许的。
正确思路：
每次操作交换位置 i 和 i+2，所以：
1. 位置 i 上的书必须和 i 同奇偶，否则无解，输出 -1。
2. 奇数位置上的书只会互相交换，偶数位置上的书也只会互相交换。
3. 最少操作次数 = 奇数位置序列变成升序的逆序数 + 偶数位置序列变成升序的逆序数。
参考代码（用归并排序求逆序数，O(N log N)）：
#include <stdio.h>
#include <stdlib.h>
long long merge(int a[], int tmp[], int l, int r) {
if (l >= r) return 0;
int mid = (l + r) / 2;
long long cnt = merge(a, tmp, l, mid) + merge(a, tmp, mid + 1, r);
int i = l, j = mid + 1, k = l;
while (i <= mid && j <= r) {
if (a <= a) tmp = a;
else {
tmp = a;
cnt += mid - i + 1;
}
}
while (i <= mid) tmp = a;
while (j <= r) tmp = a;
for (i = l; i <= r; i++) a = tmp;
return cnt;
}
int main() {
int n;
scanf("%d", &n);
int *a = (int*)malloc((n + 1) * sizeof(int));
for (int i = 1; i <= n; i++) {
scanf("%d", &a);
if (a % 2 != i % 2) {
printf("-1\n");
free(a);
return 0;
}
}
int *odd = (int*)malloc((n / 2 + 2) * sizeof(int));
int *even = (int*)malloc((n / 2 + 2) * sizeof(int));
int oc = 0, ec = 0;
for (int i = 1; i <= n; i++) {
if (i % 2 == 1) odd = a;
else even = a;
}
int *tmp = (int*)malloc((n + 1) * sizeof(int));
long long ans = merge(odd, tmp, 0, oc - 1) + merge(even, tmp, 0, ec - 1);
printf("%lld\n", ans);
free(a); free(odd); free(even); free(tmp);
return 0;
}
如果你的 N 很小，也可以分别对 odd 和 even 写冒泡统计逆序数，但要注意只比较同一序列内的相邻元素。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
页:
[1]