arrays - 从数组伪排序

Question

问题: 如果一个长度为 N 的数组 A 在最多执行一次以下操作后可以使其不减，则称该数组是伪排序的。

选择一个i，使得1≤i≤N−1并交换A_i 和 A_i+1

给定一个数组A，确定它是否是伪排序的。

输入格式
第一行包含一个整数T - 测试用例的数量。然后是测试用例。
每个测试用例的第一行包含一个整数N - 数组A的大小。
每个测试用例的第二行包含 N 个空格分隔的整数 A₁, A₂,…,A< sub>N 表示数组 A。

输出格式
对于每个测试用例，如果数组 A 是伪排序的，则输出 YES，否则输出 NO。

您可以用大写或小写打印YES和NO的每个字符(例如，yes、yEs, 是 将被视为相同)。

限制:

• 1 ≤ T ≤ 1000
• 2 ≤ N ≤ 10⁵
• 1 ≤ Ai ≤ 10⁹
• 所有测试用例的 N 总和不超过 2⋅10⁵

示例输入 1:

3
5
3 5 7 8 9
4
1 3 2 3
3
3 2 1

示例输出 1:

YES
YES
NO

我的解决方案:

#include <stdio.h>

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

但是，尽管我的代码对于给定的测试用例运行良好，但我在某些测试用例中遇到了错误。谁能帮我识别错误？

Answer 1

如果 ara 中有 n 个数字，那么算法将如下所示

#include <stdio.h>

int main() {
    int failCount = 0, i = 1, n = 3;
    int ara[3] = {3, 2, 1};
    int prevMax = ara[0] - 1;
    while ((failCount < 2) && (i < n)) {
        if (ara[i - 1] > ara[i]) {
            failCount++;
        }
        if (failCount < 2) {
            if ((i > 1) && (prevMax > ara[i])) failCount++;
            if (prevMax < ara[i - 1]) prevMax = ara[i - 1];
        }
        i++;
    }
    printf("%d", failCount);
    return 0;
}

我知道您不想读取所有数字，因此您需要在循环期间读取数字，而不是在循环之前读取所有数字，上面的代码是用于说明逻辑的简化代码。

此外，您还需要考虑诸如

之类的示例

3 1 2

其中 3 > 1 会增加计数器，但稍后您比较 1 < 2，它看起来是正确的，但是 3 也大于 2。这就是我的第二个 if 正在解决的问题。

示例测试

2 0 1