データ構造を実装する

Question

私たちはm個の異なる製品（1からmの番号が付けられています）を持っています。入札者は、m日間オープンしています。n人が購入の申し出をしています。（それぞれのオファーは1つの製品を対象としています） 毎日の終わりに、最高のオファーをもった製品（まだ販売されていないすべての製品）販売されます。

我々は、以下の操作を提供するデータ構造を実装する必要があります。

1. 初期化（M） - >提供せず、m個の要素を持つDSを初期化
2. 入札（J、P） - >のオファーを追加複雑さの製品jへの価格pで0（1）償却
3. 販売 - >最高のオファーを持つ製品を販売しています。複雑さO（対数m）で償却されたj（販売された製品）とp（製品が販売された価格）を返す。

私はfibonacceヒープを使用して、質問を解決しようとした：

• 我々は新しいFIBヒープを作成し、（キーjと情報ヌルで製品）m回を挿入

• 私はフィックスヒープの減少キーのアイデアを使用して、新しいpに情報を切り替えます

• 私はdelete minというアイデアを使って最大値を削除します

この問題を解決するには、最大ヒープと最小ヒープを使用しないといけないと思うので、間違っていると思います。

誰かが真のソリューションを手に入れるのに役立つでしょうか。 **

Answer 1

商品のハッシュテーブルを最大入札価格に保ち、Bid（）とO（1）をSell（）にO（log M）、最大入札でソートした商品リストを得ることができます。

Bid（）では、必要に応じてテーブルを更新し、必要に応じてリストをバイナリ検索で更新します。 Sell（）では、リストから一番上の項目をポップし、地図から価格を取得するだけです。