c++ - Coursera 自动评分器给我未知信号 11

Question

我正在上一门算法课，现在我们正在学习贪婪算法。我的两个解决方案在某些测试用例上输出“未知信号 11”。

但是，我用尽可能大的输入将我的程序推向了极限。它在我的电脑上运行得很好。然而，在 Coursera 的评分器上，它会抛出未知信号 11 的神秘消息。

如果我改用Python，这个问题会消失吗？

这是显示问题的第一个代码:

 #include <iostream>
 #include <utility>
 #include <algorithm>
 using namespace std;

bool sortAlg(pair<double, pair<uint64_t,uint64_t>> item1, pair<double, 
pair<uint64_t,uint64_t>> item2)
{
return (item1.first >= item2.first);
}
int main()
{
uint64_t n, index = 0;
double W, val;
cin >> n >> W;
pair<double, pair<uint64_t,uint64_t>> items[n];
for (int i=0; i <n; i++)
{
    cin >> items[i].second.first >> items[i].second.second;
    items[i].first =  (double)items[i].second.first / (double)items[i].second.second;
}
sort(items,items+n, sortAlg);

while(W > 0 && n > 0)
{
    if (items[index].second.second <= W)
    {

        val += items[index].second.first;
        W -= items[index].second.second;
        index++;
        n--;
    }
    else
    {
        val += items[index].first * W;
        W = 0;
        index++;
        n--;
    }
}
printf("%.4f",val);
return 0;
}

我认为这与 while 循环有关，但我想不出程序会使用索引进行越界数组调用的任何地方。

无论如何，它是一个分数背包实现。

这是第二个代码，它也给出了未知信号 11:

#include <iostream>
#include <string>
#include<vector>
#include <algorithm>
#include <utility>
using namespace std;

bool sortAlg(string num1, string num2)
{
    if (num1[0] > num2[0]) return true;
    else if (num1[0] < num2[0]) return false;
    else
{
    if (num1.size() == 1 && (num1[0] > num2[1])) return true;
    else if (num1.size() == 1 && (num1[0] < num2[1])) return false;
    else if (num2.size() == 1 && (num1[1] > num2[0])) return true;
    else if (num2.size() == 1 && (num1[1] < num2[0])) return false;
    else if (num1 == "1000" || num2 == "1000") return (num1 < num2);
    else
    {
        if (num1.size() == num2.size()) return (num1 > num2);
        else
        {
            return (num1[1] > num2[1]);
        }
    }
}
}

int main()
{
string num;
int n, n2 = 1;
cin >> n;
//int numbers[n];
vector<string> numbers2;
for (int i =0; i <n; i++)
{
    num = to_string(n2);
    cout << num << endl;
    numbers2.push_back(num);
    n2 += 10;
}
sort(numbers2.begin(), numbers2.end(), sortAlg);

for (auto number : numbers2)
{
    cout << number;
}
return 0;
}

我怀疑排序函数中使用了sortAlg函数，但在我的电脑上它相对较快。问题陈述需要一些奇怪的排序。

问题是给定一组数字，排列它们以使数字尽可能大。

例如，如果给出 9, 98, 2, 23, 21，它应该给我 99823221。(9 > 98 > 23 > 2 > 21)所以我按第一个数字排序，然后是下一个数字，依此类推。

Answer 1

您遇到 StackOverflow 错误。

必要的堆栈大小取决于递归的深度、递归函数的参数数量以及每个递归调用内的局部变量的数量。

在 Python 中，您必须设置必要的堆栈大小。 Python 3 中提供的入门文件将具有以下示例:

import threading

sys.setrecursionlimit(10 ** 6)  # max depth of recursion
threading.stack_size(2 ** 27)  # new thread will get stack of such size
...
threading.Thread(target=main).start()

注意stack_size是如何分配的。