私はOJの古典的なTOPK問題を解決しようとしています：配列を与えられて、最大の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 45445654 34 44 5645 68455 32 56 51 63 47453554655 761 10
出力：5645 2132 761 655 654 554 455 453 445 68
あなたのコードは間違っています。のあいまいな呼び出しsize（mysizeなどの別の呼び出し）を無視すると、コードのどこかで範囲を超えているように見えます。
あなたの例でNは、は19に等しいので、maxHeap配列には0から19-1 = 18までのインデックスを付ける必要があります。
ただし、ここでは、たとえば、19にアクセスします。
for ( pos; maxHeap[pos / 2] <= item; pos /= 2 )
maxHeap[pos] = maxHeap[pos / 2];
posあなたが私を信じていない場合は、ループの本文にの印刷ステートメントを追加してください。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加