1

入力を 2 次元配列で取得し、それを行単位で最速の方法でソートできる方法が必要です。を使ってInputとSortを同時に取ってみInsertion Sortました。私が使用した2番目のことはmultimap、行を個別に取得し、必要な値としてキー値を挿入し、マップされた値がそのキーにダミー値として関連することです。map は挿入中にキーをソートするので、私が考えた 1 つの方法である可能性があります。

以下のコードは、2D の 1 行の要素が multimap でソートされていることを確認するためのものです。基本的に、これらの行を 1 つずつ個別に使用するため、1D 配列と見なすことができるため、2D 構造をまったく使用したくないと言えます。また、 Input の読み取り中にそれらを再配置したいので、それらを実行するために余分な操作を行う必要はありません。 

for(long int j=1;j<=number_in_group;j++)
{
   cin >> arrival_time;
   arrival_map.insert(pair<long int, long int>(arrival_time,1));
}
4

1 に答える 1

1

STL std::priority_queue?を試してください。出力はソートされることが保証されており、入力を 2-D オブジェクト (たとえば、行番号を含む) に極性化すると、キューは文字通り完全に構築されます。その時点で、「n」のバッチでキューから番号を丸呑みするだけです。「n」は行サイズであり、それぞれが正しくソートされます。プライオリティ キュー内の値と行の両方をエンコードし、最初に行 # に偏って並べ替え、次に値にする要素タイプが必要になります。あなたの例ではlong int、値のデータ型として使用しています。行がシステムの unsigned int のサイズよりも大きくないと仮定します。

class Element
{
public:
   Element(unsigned int row, long int val)
      : myrow(row), myval(val)
   {};

   bool operator <(const Element& elem)
   {
      return (myrow < elem.myrow || 
             (myrow == elem.myrow && myval < elem.myvel);
   }

   unsigned int myrow;
   long int myval;
};


typedef std::priority_queue<Element> MyQueue;

std::less<>注: これは、 item-defined を使用してアイテムを単純に比較する優先キューのデフォルトの比較演算子 invokingを利用していますoperator <()。これを取得したら、行列をキューにプッシュし、次の行に切り替えるときに行インデックスをインクリメントします。

MyQueue mq;

mq.push_back(Element(1,100));
mq.push_back(Element(1,99));
mq.push_back(Element(2,100));
mq.push_back(Element(2,101));

終了時にキューをポップすると、次のシーケンスになります: 99 100 100 101

あなたが望むものであることを願っています。最後に、構文エラーやジャンクの欠落を許してください。私はこれをその場で爆破しただけで、チェックするコンパイラがありません。ウェブカフェが大好きです。

于 2012-07-22T09:01:03.360 に答える