时间戳

首页 > 解决方案 > 对 Google CodeJam 2018 预选赛进行故障排序

c++ - 对 Google CodeJam 2018 预选赛进行故障排序

问题描述

我正在尝试通过解决几个 Code Jam 问题来提高我的编程技能。我在 2018 年预选赛的“问题排序”问题上被困了一段时间。我的代码在控制台中使用示例输入产生了预期的输出，但在线评委返回“错误答案”。

显然，麻烦排序就像冒泡排序一样，除了比较第 i 个和第 i+1 个元素之外，它比较第 i 个和第 i+2 个元素，如果前者大于后者，则交换元素。这个问题说这个算法是有缺陷的，因为像 897 这样的数组在故障排序后将返回 798，它也没有排序。任务是检查对于给定的整数列表，故障排序是否能够成功地对数组进行排序，或者如果不是，那么第一个元素的索引值不合适。

我的代码输入测试的数量 t 和整数列表的大小。然后我复制一份，将一份通过冒泡排序，另一份通过故障排序。然后我逐元素比较它们，如果找到具有两个元素作为不同整数的索引，则将其输出。我不确定我在这里做错了什么。

    #include<iostream>
    #include<vector>

    using std::cin;
    using std::cout;
    using std::endl;
    using std::string;
    using std::vector;

    void swapVal(int& a, int& b)
    {
        int t = a;
        a = b;
        b = t;
    }

    int main()
    {
        int t;
        cin >> t;
        for (int i = 1; i <= t; i++)
        {
            int n;
            cin >> n;
            vector<int> bs(n);
            vector<int> ts(n);

            for (int i = 0; i < n; i++)
            {
                cin >> bs[i];
                ts[i] = bs[i];
            }

            //bubbleSort(bs, n);

            {
                bool bsSorted = false;
                while (!bsSorted)
                {
                    bsSorted = true;
                    for (int i = 0; i < n - 1; i++)
                    {
                        if (bs[i] > bs[i + 1])
                        {
                            swapVal(bs[i], bs[i + 1]);
                            bsSorted = false;
                        }
                    }
                }
            }

            //troubleSort(ts, n);
            {
                bool tsSorted = false;
                while (!tsSorted)
                {
                    tsSorted = true;
                    for (int i = 0; i < n - 2; i++)
                    {
                        if (ts[i] > ts[i + 2])
                        {
                            swapVal(ts[i], ts[i + 2]);
                            tsSorted = false;
                        }
                    }
                }
            }

            bool same = true;
            int minidx = 0;
            for (int i = 0; i < n; i++)
            {
                if (bs[i] != ts[i])
                {
                    same = false;
                    minidx = i;
                    break;
                }
            }

            if (same == true)
            {
                cout << "Case #" << i << ": OK" << endl;
            }
            else if (same == false)
            {
                cout << "Case #" << i << ": " << minidx;
            }
        }
    }

我期待法官给我一个批准，但它却一再返回“错误答案”。我在这里做错了什么？

标签： c++sorting

解决方案

该算法对我来说看起来是正确的。我注意到在错误的情况下，您似乎缺少换行符。所以两个连续的错误陈述将在同一行。

cout << "Case #" << i << ": " << minidx<<'\n';

或许能解决你的问题。

几点说明：

  • if (same == true)等价于if(same)和。if (same == false)if(!same)
  • 已经有了std::swap。
  • 有些人可能不喜欢具有同名变量的嵌套 for 循环 - 嵌套变量将隐藏外部变量。

推荐阅读