POJ 1456 Supermarket解題まとめ

Honor Statement:自分では書いていないので、ネット上の解答を参考にして書きました.アルゴリズムはオリジナルではありませんが、文章の内容は自分で書いたものです.
言語:C++(実はC++の中のものはあまり使われていません)
アルゴリズム思想:貪欲なアルゴリズム.各productのprofitが大きいものから小さいものまで順番に各productがいつ販売されるかを決定します.決定の根拠は簡単で、deadlineに他のproductが配置されている場合は、前に探して、最初に物品を手配したことがない時点がその貨物の販売時間です.見つからない場合は、deadlineの前に他のアイテムが配置されており、各アイテムがその価値より高いことを示します(価値の高いアイテムが先に配置されているため).では、この貨物は利益が最も高い時のsellリストに入ることはできません.具体的な手順は次のとおりです.
0.コンソールからデータを受信し、データを受信する際に、入力したデータの中で最大のdeadlineが何であるかを統計し、max_と記入するdeadline.疑似コードで次のように説明します.
int max_deadline = -1;//Initialize
while(…){
….//受信データ
If ( the deadline you got is greater than max_maxline )
then max_deadline = the deadline you got
else do nothing
}
1.入力したデータペアをprofitに従って大きいから小さいまで並べ替えます.Productクラスを定義し、profitとdeadlineをクラスメンバーとし、クラスに演算子'を再ロードすると、C++のsort関数(#inlcude)でソートできます.もちろん、自分でcompare関数(フォーマットは娘や谷哥之)を書いて、sort関数を呼び出すときにコールバック関数として渡すこともできます.(*注1)順序を決めてから2ステップ目を行います.並べ替えたデータ対配列をproducts,products[0]をprofit最大のデータ対とする.
2.max_の長さを定義deadlin+1のint型配列をsellと記す.配列をゼロに初期化します(memsetで初期化することをお勧めします.
3.i=0とする. 
4.sell配列のproducts[i].deadlineの数値がゼロであるif(sell[products[i].deadline==0)ではsell[products[i].deadline] = products[i].profit.sell配列のproducts[i].deadlineの数値はゼロではありません.これは、価値の高いものが配置されていることを示しています.大きい順に走査するsell配列の下付きはproducts[i]より小さい.deadlineの各要素は、最初にゼロの要素を見つけて、次のステップに進みます.
5.sell配列の0番要素でない場合、その要素=products[i]とする.profit.
6.要素のグループが処理されたら、次のステップに進みます.そうしないと、i++になってから4番目のステップに進みます.
7.ファイルの最後まで行かない場合は、手順0を実行します.そうしないと、プログラムは終了します.
アルゴリズムの正確性の分析(非証明):profitの高い品物は先に売るように手配します.そのため、高利益の貨物ができるだけ売れるまで、低利益の貨物は売れません.
アルゴリズムまとめ:アルゴリズムは最悪の場合に時間複雑度がO(n*n),空間複雑度がO(1)である.時間は主に、各貨物がdeadlineを検索する前に(deadlineを含む)最初に貨物を手配していない時点に費やされます.最悪の場合例:すべての貨物のdeadlineがmax_deadline.
アルゴリズムの改善:荷物を手配していない時点をどのように検索するかを改善することから着手することができます.
解決すべき疑問点:
1.ある解法は、並べて収集したり、線分の木を調べたりするなどの方法で解決できると言っていますが、能力が限られていて、これらが何なのかはしばらく分かりません.スタックを使いすぎたが、考えが間違っていて、OJはタイムアウトや間違った答えを言った.
2.アルゴリズムには厳密な証明が欠けている.『Algorithm Design』の貪欲アルゴリズムの章の証明構想で証明できると思います.
実装コード:

#include 
#include 
#include 
#include 
#include 
#define MAX_PRODUCT 10005
using namespace std;
class Product{
public:
	int deadline;
	int profit;
	bool operator < (const Product& rop) const {
		return  rop.profit < profit;
	}
};

 int main(){
	 int profit[MAX_PRODUCT];
	 Product* products = new Product[MAX_PRODUCT];
	 int sum, num,i,max_deadline,j;
	 string s;
	 while ( cin >> s ){
		 sum = 0;
		 i = 0;
		 max_deadline = -1;
		 num = atoi ( s.c_str() );
		 while( i < num  ){
			 cin >> s;
			 products[i].profit = atoi ( s.c_str() );
			 cin >> s;
			 products[i].deadline = atoi ( s.c_str() );
			 if ( products[i].deadline > max_deadline )
				 max_deadline = products[i].deadline;
			 i++;
		 }
		 memset(profit,0, (max_deadline+1)*sizeof(int));
		 sort( products, products + num );
		 for( i = 0; i < num; i++ ){
			if( profit[ products[i].deadline ] == 0 )
				profit[ products[i].deadline ] = products[i].profit;
			else{
				for( j = products[i].deadline -1;;j-- )
					if( profit[j] == 0 )
						break;
				if ( j != 0 ) profit[j] = products[i].profit;
			}
		 }
		 for ( i = 1; i <= max_deadline; i++ )
			 sum += profit[i];
		 cout << sum << endl;
	 }
	 return 0;
 }

 
*注1:同じ価値の貨物はdeadlineを大きく先に手配すべきだという解法がありますが、個人的には必要ないと思います.
*注2:コンソールにEOFを入力する方法:Ctrl+Z、Enter.