C++ 从数组伪排序

您的测试统计两个相邻数字出现故障的情况数.这还不足以解决这个问题.下面是一个反例:

1
3
3 1 2

3 1 2产生1的count，但需要2次互换.

一旦检测到某个元素出现故障，必须测试将其与前一个元素交换是否可以解决问题:

#include <stdio.h>

int main() {
    int T = 0, ara[100000], count, i, j;
    scanf("%d", &T);
    for (i = 0; i < T; i++) {
        int N = 0;
        scanf("%d", &N);
        for (j = 0; j < N; j++) {
            ara[j] = 0;
            scanf("%d", &ara[j]);
        }
        count = 0;
        for (j = 1; j < N && count < 2; j++) {
            if (ara[j] < ara[j - 1]) {
                int temp = ara[j - 1];
                ara[j - 1] = ara[j];
                ara[j] = temp;
                count++;
                if (j > 1) {
                    j -= 2;
                }
            }
        }
        if (count <= 1) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

一旦发现故障，您可以删除数组并避免转换剩余的数字:

#include <stdio.h>

int main() {
    int T = 0, i, j;
    scanf("%d", &T);
    for (i = 0; i < T; i++) {
        int N = 0, n1 = 0, n2 = 0, n3, count = 0, c, temp;
        scanf("%d", &N);
        if (N >= 2) {
            scanf("%d%d", &n1, &n2);
            if (n1 > n2) {
                temp = n1;
                n1 = n2;
                n2 = temp;
                count++;
            }
            for (j = 2; j < N; j++) {
                n3 = 0;
                scanf("%d", &n3);
                if (n2 > n3) {
                    count++;
                    if (count > 1)
                        break;
                    if (n1 > n3) {
                        count++;
                        break;
                    }
                    n1 = n3;
                } else {
                    n1 = n2;
                    n2 = n3;
                }
            }
        }
        /* read and discard the rest of the line */
        while ((c = getchar()) != EOF && c != '\n')
            continue;
        if (count <= 1) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}