时间戳

首页 > 解决方案 > 如何解决 OJ 上的“运行时错误”

c++ - 如何解决 OJ 上的“运行时错误”

问题描述

我正在尝试解决 OJ 上的经典 TOP K 问题：给定一个数组，计算最大的 K 数并按升序输出它们。我的解决方案是构建一个 MAX ROOT HEAP，并删除 K 次。当我将它们放在 OJ 上时，它告诉我“运行时错误”并给了我正确的输入和输出。但我下载了输入文件并在我自己的 PC 上测试，这是正确的。那么我的代码有什么问题？是否有任何非法操作导致“运行时错误”？

#include <iostream>
using namespace std;

long long N,K;
long long * maxHeap;
long long size = 0;

void insertItem(long long * maxHeap)
{
    long long item;
    cin >> item;
    long long pos = ++size;
    for  ( pos; maxHeap[pos / 2] <= item; pos /= 2 )    maxHeap[pos] = maxHeap[pos / 2];
    maxHeap[pos] = item;
}

long long deleteItem(long long * maxHeap)
{
    long long max_item = maxHeap[1];
    long long item = maxHeap[size--];
    long long parent = 1;
    long long child;
    for ( parent; parent * 2 <= size; parent = child ) {
        child = parent * 2;
        if ( child < size && maxHeap[child] < maxHeap[child + 1] )  child++;
        if ( item > maxHeap[child] )    break;
        else    maxHeap[parent] = maxHeap[child];
    }
    maxHeap[parent] = item; 
    return max_item;
}

int main()
{
//  freopen("F://input.txt","r",stdin);
    cin >> N;
    maxHeap = new long long[N];
    maxHeap[0] = 1000000000;
    for ( long long i = 0; i < N; i++ ) insertItem(maxHeap);
    cin >> K;
    for ( long long i = 0; i < K; i++ ) cout << deleteItem(maxHeap) << endl;
    delete[] maxHeap;
    return 0;
}

从 OJ 下载的输入样本：19 11 2132 45 445 654 34 44 5645 68 455 32 56 51 63 47 453 554 655 761 10

输出：5645 2132 761 655 654 554 455 453 445 68

标签： c++arrays

解决方案

你的代码是错误的。忽略对（将其称为其他名称，例如 mysize）的模棱两可的调用size，您似乎在代码中的某个地方越界了。

在您的示例中，N等于 19，因此您的maxHeap数组应从 0 索引到 19-1=18。

但是，在这里，例如，您可以访问 19：

for  ( pos; maxHeap[pos / 2] <= item; pos /= 2 )
    maxHeap[pos] = maxHeap[pos / 2];

pos如果您不相信我，请在循环体中添加 print 语句。

推荐阅读