如果功能在冰点之后存在，则程序冻结

Question

当函数 analiza() 未被注释时，我的程序会在 input() 函数中显示两条消息。 (przed, po), 但是，如果我在 input() 之后取消注释 analiza()，它就会中断。我尝试清理缓冲区、不同的库等。没有任何帮助。代码：

#include <iostream>
using namespace std;

unsigned int liczba_osob, liczba_klapek, przeszli = 0;
unsigned long long osoby[200000], klapki[200000], minimum;
bool do_uzycia[200000]{0};

unsigned long long greatest();
bool czy_mozliwe(unsigned int osoba);
void input();
void analiza();

int main()
{
    input();
  analiza();
    return 0;
}

unsigned long long greatest()
{
    unsigned long long maxrn = klapki[0];
    for (unsigned int i = 1; i < liczba_klapek; i++)
        if (klapki[i] > maxrn)
            maxrn = klapki[i];
    return maxrn;
}

bool czy_mozliwe(unsigned int osoba)
{
    if (osoby[osoba] >= minimum)
        return 1;
    unsigned long long maximim = greatest();
    if (osoby[osoba] + maximim < minimum)
        return 0;
    for (unsigned int i = 0; i < liczba_klapek; i++)
    {
        if (osoby[osoba] + klapki[i] >= minimum && !do_uzycia[i])
        {
            do_uzycia[i] = 1;
            return 1;
        }
    }
    return 0;
}
void input()
{
    cin >> liczba_osob;
    for (unsigned int i = 0; i < liczba_osob; i++)
        cin >> osoby[i];

    cin >> liczba_klapek;
    for (unsigned int i = 0; i < liczba_klapek; i++)
        cin >> klapki[i];
cout<<"przed";
    cin >> minimum;
    cout<<"po";
}
void analiza()
{
     for (unsigned int i = 0; i < liczba_osob; i++)
        if (czy_mozliwe(i))
            przeszli++;
    cout << przeszli;
}

因此，问题 rn 与输入有关：

200000
10 20 30... (and 199997 times more)
200000
10 20 30... (and 199997 more)
2500000

由于数组长度为 200000，所以最大输入。程序在 cout<<"przed"; 之后的 input() 冻结。它没有得到最小变量的输入。如果我在 int main() 中删除对 analiza() 的调用，问题就不会发生。

这是造成问题的输入文件file

Answer 1

对于给定的输入，您的函数 analiza 对函数 czy_mozliwe 进行了 200000 = 2 * 10^5 次调用。该函数依次调用 greatest，它使循环迭代 2 * 10^5 次并在每次迭代中进行比较，然后 czy_mozliwe 继续运行它自己的循环，其中包含 2 * 10 ^5 次迭代。

所以为了完成analiza的执行，计算机需要执行greatest中循环的4 * 10^10次迭代和[=中循环的4 * 10^10次迭代11=].

这可能需要很长时间。

与此同时，您在 cout<<"po"; 中排队的输出可能只是在缓冲区中等待。你没有看到它出来是因为你写的时候没有刷新缓冲区。请尝试 cout<<"po"<<std::endl;。

然后您可能会考虑如何编写您的程序，这样它的内部循环就不需要那么多次迭代。

如果功能在冰点之后存在，则程序冻结

Program freezing if function is present after the freezing point

c++

for-loop

cin