3

Θ(N+klogN)オンラインジャッジで、時間計算量のあるN個の要素の順序付けられていないセットからk個の最大要素を見つける関数を設計したいと思います。

ここにサンプルがあります：

入力

LN 1 : N K

LN 2 : N numbers

出力

LN 1 : K biggest number

LN 2 : Final heap

サンプル入力

10 4
17 19 26 37 30 11 5 29 32 1

サンプル出力

29
26 19 11 17 1 5

そしてここに私のコードがあります：

#include <iostream>

using namespace std;

int main(){

    int i,j,rc,temp,temp1,length,K;
    cin>>length>>K;
    int *heap = new int[length];

    for(i=0;i<length;i++) cin>>heap[i];
    for(i=length/2-1;i>=0;i--){                  //build a max heap first with Θ(N)
        while(!((i>=length/2)&&(i<length))){
            j = 2*i+1;
            rc = 2*i+2;
            if((rc<length)&&(heap[j]<heap[rc])) j=rc;
            if(heap[i]>heap[j]) break;
            temp = heap[i];
            heap[i]=heap[j];
            heap[j]=temp;
            i=j;
        }
    }
    int k,n=length;
    for(k=0;k<K;k++){                         //shiftdown k times to find k biggest 
        temp1=heap[--n];                      //numbers with Θ(klogN)
        heap[n] = heap[0];
        heap[0] = temp1;
        if(n!=0) {
            i=0;
                while(!((i>=n/2)&&(i<n))){
                     j = 2*i+1;
                    rc = 2*i+2;
                    if((rc<n)&&(heap[j]<heap[rc])) j=rc;
                    if(heap[i]>heap[j]) break;
                    temp = heap[i];
                    heap[i]=heap[j];
                    heap[j]=temp;
                    i=j;
                }
            }
        }


    cout<<heap[length-K]<<endl;
    for(i=0;i<length-K;i++)
        cout<<heap[i]<<" ";
    return 0;
}

大丈夫ですが、データの1つがTime Limit Exceedです。この問題を解決する方法に、私はとても混乱しています。

4

3 に答える 3

0

ふるいにかける操作が正しくないようです。そこに2つのネストされたループがあってはなりません。ルートから始めて、両方より大きくなるまで、その子の1つと交換し続ける必要があります。外側のループfor(i=n/2-1;i>=0;i--)はそこにあるべきではありません（これにより、各シフトダウンが実行されます）-ルートから開始するには、0にO(n)設定する必要があると思います。i

編集：あなたのheapify操作も遅すぎます：あなたはi外側と内側のループの両方に同じループ変数を使用しているので、それは交互に大きくなり、小さくなります。内側のループは外側のループので始まる必要がありますが、外側のループの次の反復でのi値に影響を与えるべきではありません。iふるい分け操作を独自の機能に組み込むことをお勧めします。これにより、この問題が修正され、ふるい分けが2回コーディングされるのを防ぐことができます。

于 2012-11-04T09:53:17.853 に答える
0

私が推測するいくつかのonlinejudge.orgコンテスト。問題のリンクを共有してみませんか？

次に、ヒープソートが本当に必要かどうか、またはQuickSelectや優れたヒューリスティックのようなものを使用したほうがよいかどうかを判断できます。

私の推測では、単純なヒープソートは、テストケースの1つには十分ではありません。

おそらく、最初と最後に、事前に並べ替えられたデータのチェックや、逆に並べ替えられたデータ（およびデータ部分）のチェックなどの最適化を追加する必要があります。これらのパーツのヒープを構築することは避けますが、そのままにしておきます。

最悪の場合である大きなk、IIRCを使用して、巨大な逆ソートリストでヒープソートを実行してみてください（最大ヒープの場合、最小ヒープは最悪の場合であり、その逆です）。

典型的なオンラインジャッジテストケースは、通常、そのような既知の最悪のケースを中心にうまく設計されています。そして、制限時間は、非常に優れた最適化されO(n + k log n)たソリューションでも、真のO(n)ソリューションと比較して失われるように設定されます。kを十分に大きくする必要があります。彼らはコンテストからのものであり、彼らは彼らに本当の平均的な入力ファイルを与えることによって人々に挑戦したいと思っています！

PSYouヒープビルドも複雑すぎるようです。問題は、あなたが再び増加することです。iこれを行う必要はありません。whileループでiを増やすと、ボトムアップヒープ構造が複数回「再起動」されます。したがって、ヒープビルドはおそらくもうありませんO(n)。

于 2012-11-04T09:53:57.977 に答える
0

次の3つの異なるシーケンスで何が起こるかを確認することをお勧めします。

    1. 4 2 1 2 3 4
    1. 4 2 4 3 2 1
    1. 4 2 1 1 1 1
 int NN=0;
 for(i=length/2-1;i>=0;i--){                  //build a max heap first with Θ(N)
cout << "i=" << i << "\n";
    while(!((i>=length/2)&&(i<length))){
        j = 2*i+1;
        rc = 2*i+2;
        cout << NN++ << " " << j << " " << rc << " " << i << "\n";
        if((rc<length)&&(heap[j]<heap[rc])) j=rc;
        if(heap[i]>heap[j]) break;
        temp = heap[i];
        heap[i]=heap[j];
        heap[j]=temp;
        i=j;
    }
}

最後のケースでは、ループはj=3に安定します。rc = 4; i = 1;

おそらく、内部ループは「i」の代わりに別の変数を使用する必要があります。

于 2012-11-04T11:58:29.000 に答える