这个冒泡到底哪里有问题

李星彤

新生入学后，图书馆将
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[100005];
  for(int i = 0; i < n; i++)
  {
    scanf("%lld",  &a[i]);
    if(a[i] % 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[i] > a[i + 2])
    {
      long long t = a[i];
      a[i] = a[i + 2];
      a[i + 2] = t ;
      ans++;
    }
  }

  printf("%lld", ans);
  return 0;
}

FishC

你的代码主要有这些问题：

• a 只是一个变量，没有数组，读入时每次都覆盖，后面无法比较和交换。
• 奇偶检查的 if 没有大括号，导致 printf("-1"); return 0; 无论条件如何都会执行，程序读第一个数就退出了。
• 冒泡里写的是 a > a，自己和自己比，永远不成立；而且交换的也是同一个变量，没有意义。
• 循环边界 n-2 不对，且没有对数组操作。
• 不能对整个数组直接冒泡排序。题目每次只能交换距离为 2 的两个位置，也就是只能交换奇数位置之间、偶数位置之间。直接冒泡会交换相邻的奇偶位置，这是不允许的。
  

正确思路：
每次操作交换位置 i 和 i+2，所以：
1. 位置 i 上的书必须和 i 同奇偶，否则无解，输出 -1。
2. 奇数位置上的书只会互相交换，偶数位置上的书也只会互相交换。
3. 最少操作次数 = 奇数位置序列变成升序的逆序数 + 偶数位置序列变成升序的逆序数。

参考代码（用归并排序求逆序数，O(N log N)）：

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. 
   
5. long long merge(int a[], int tmp[], int l, int r) {
   
6.     if (l >= r) return 0;
   
7.     int mid = (l + r) / 2;
   
8.     long long cnt = merge(a, tmp, l, mid) + merge(a, tmp, mid + 1, r);
   
9.     int i = l, j = mid + 1, k = l;
   
10.     while (i <= mid && j <= r) {
    
11.         if (a[i] <= a[j]) tmp[k++] = a[i++];
    
12.         else {
    
13.             tmp[k++] = a[j++];
    
14.             cnt += mid - i + 1;
    
15.         }
    
16.     }
    
17.     while (i <= mid) tmp[k++] = a[i++];
    
18.     while (j <= r) tmp[k++] = a[j++];
    
19.     for (i = l; i <= r; i++) a[i] = tmp[i];
    
20.     return cnt;
    
21. }
    
22. 
    
23. int main() {
    
24.     int n;
    
25.     scanf("%d", &n);
    
26.     int *a = (int*)malloc((n + 1) * sizeof(int));
    
27.     for (int i = 1; i <= n; i++) {
    
28.         scanf("%d", &a[i]);
    
29.         if (a[i] % 2 != i % 2) {
    
30.             printf("-1\n");
    
31.             free(a);
    
32.             return 0;
    
33.         }
    
34.     }
    
35.     int *odd = (int*)malloc((n / 2 + 2) * sizeof(int));
    
36.     int *even = (int*)malloc((n / 2 + 2) * sizeof(int));
    
37.     int oc = 0, ec = 0;
    
38.     for (int i = 1; i <= n; i++) {
    
39.         if (i % 2 == 1) odd[oc++] = a[i];
    
40.         else even[ec++] = a[i];
    
41.     }
    
42.     int *tmp = (int*)malloc((n + 1) * sizeof(int));
    
43.     long long ans = merge(odd, tmp, 0, oc - 1) + merge(even, tmp, 0, ec - 1);
    
44.     printf("%lld\n", ans);
    
45.     free(a); free(odd); free(even); free(tmp);
    
46.     return 0;
    
47. }
    

复制代码

如果你的 N 很小，也可以分别对 odd 和 even 写冒泡统计逆序数，但要注意只比较同一序列内的相邻元素。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。