3-09. キュー内の要素のソート【pat】

3-09. キュー内の要素のソート
時間の制限
50 ms
メモリ制限
32000 kB
コード長制限
8000 B
クイズルーチン
Standard
キューを指定するには、次のような合法的なキュー操作関数を使用します.
(1) int IsEmptyQ(Queue Q) (2) void AddQ(Queue Q, ElementType item) (3) ElementType DeleteQ(Queue Q)
キュー内の要素を小さいものから大きいものに並べ替えます.
注意:キュー(配列)の要素に直接アクセスするには、配列の下に表示されません.補助キューを使用します.ソート後の結果は元のキューに保存します.
フォーマットの説明を入力:
入力は、まず1つの正の整数N(<=105)を与え、キュー内の要素の個数を表す.その後、N個の整数がエンキューの順序で与えられる(ここではitemが整数値であると仮定する).
出力フォーマットの説明:
ソート後にデキューされたシーケンスを1行に出力します.数字の間はスペースで区切られていますが、末尾に余分なスペースを入れてはいけません.
サンプルの入力と出力:
シーケンス番号
入力
しゅつりょく
1

10 9 4 6 1 8 3 7 0 2 5

0 1 2 3 4 5 6 7 8 9

【結題報告】:この問題は面白いですね.一見普通の並べ替え問題だと思います.条件をよく見ると、2つのキューとその合法的な操作しかできず、下付き文字にアクセスできません.出題者の意図は、あなたが並べ替えアルゴリズムをシミュレートする過程を考えることです.並べ替えアルゴリズムは数種類あります.複雑度O(N^2)のはきっとだめで、問題の設定時間は50 msしかありません.残りは集計ソートかクイックソートかもしれません.条件制限は下付き文字にアクセスできません.セカンダリスペースにもキューが1つしかありません.quick sortはだめだと思います.すぐにデータを交換しなければならないので、チェーンテーブルがデータを巡るときは不便です.では、merge sortの方向に考えてみましょう.mergeの考え方は簡単にグループに分けて、グループ内でソートしてからグループ間でソートします.3つのキューが必要です.2つを統合して3番目に入れます.しかし、タイトル自体は2つのキューしかないので、結果はどこに置きますか.答えは:元のキューの末尾!ここまで考えてみればわかる.

#include
#include
#include
#include
using namespace std;

deque que1;
deque que2;

void print_q(deque que)
{
	bool first=true;
	while(!que.empty())
	{
		if(!first)
			printf(" %d",que.front());
		else
			printf("%d",que.front());
		first=false;
		que.pop_front();

	}

}
void merge_sort(int n,int m,deque& que,deque& que2) 
{
	int i=0,j=0;
	i=0;
	j=0;
	while(i&que_out,deque& que_in)
{
	int i=0;
	for(i=0;i& que,deque& que2)
{
	int i=0;
	if(n!=1)
		merge_div(n/2,n-n/2,que,que2);
	if(m!=1)
		merge_div(m/2,m-m/2,que,que2);
	if((n==1&&m==1))
	{   
		que2.push_back(que.front());
		que.pop_front();
		merge_sort(n,m,que,que2);
	}
	else//if m n doesn't equal 1 they should be combine with other nums
	{  
		if(n==1)
		{
			 que_pop(m,que,que2);
			 merge_sort(m,n,que,que2);
		}
		else if(m==1)
		{
		   que_pop(n,que,que2);
		   merge_sort(n,m,que,que2);
		}  
		else
		{
		    que_pop(m,que,que2);
			que_pop(n,que,que);
			merge_sort(m,n,que,que2);
		}
	}
}

int main()
{
	int n=0,i=0;
	int temp=0;

	while(scanf("%d",&n)!=EOF)
	{ 
		////////
		//	n=100;

		//int time_s=time(NULL);
		for(i=0;i

デバッグするときは(1)(1 m)(n 1)のような場合に注意しましょう.