白準1021号:回転キュー

リンク:https://www.acmicpc.net/problem/1021queueライブラリを使用します.資料の構造はいろいろしました.でも書く時にarrayを親にするqueueを後悔しました.queueはインデックスへのアクセスが最も悪い.
注意:https://twpower.github.io/76-how-to-use-queue-in-cpp
わっと殴られた!

次回もしっかり編んで、一度で合って

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

void secondfunc(queue<int>& que); 

void thirdfunc(queue<int>& que);

int main() {
	int num, out, answer = 0;
	cin >> num >> out;
	
	queue<int> que;
	for (int i = 1; i <= num; i++) {
		que.push(i);
	}

	int key;
	while (out != 0) {
		int idx = -1;
		cin >> key;

		int total = que.size();
		int mid = (total / 2);
		
		for (int j = 0; j < total; j++) {		
			int elmt = que.front();	
			if (key == elmt)
				idx = j;
			que.pop();
			que.push(elmt);
		}

		if (idx <= mid ) {
			for (int i = 0; i < idx; i++) {
				secondfunc(que);
				answer++;
			}
		}

		else {
			for (int i = idx; i <total; i++) {
				thirdfunc(que);
				answer++;
			}
		}

		que.pop();
		out--;
	}
	cout << answer << endl;
	return 0;
}


void secondfunc(queue<int>& que) {
	int tmp = que.front();
	que.pop();
	que.push(tmp);
}

void thirdfunc(queue<int>& que) {
	int tmp = que.back();
	int num = que.size() - 1;
	queue<int> temp;
	temp.push(tmp);
	int front;
    
	for (int i = 0; i< num; i++) {
		front = que.front();
		temp.push(front);
		que.pop();
	}
	while (!que.empty()) {
		que.pop();
	}
	for (int i = 0; i < num + 1; i++) {
		front = temp.front();
		que.push(front);
		temp.pop();
	}
}

最終的に、実装はキューライブラリ内の回転キューの性質を十分に発揮していない.circle queue..

for (int j = 0; j < total; j++) {		
    int elmt = que.front();	
    if (key == elmt)
    	idx = j;
    que.pop();
    que.push(elmt);
}

まず、最初のキューなのでインデックスでアクセスできないので、for文で1回回転して検索するアイテムのインデックスを探す方法から始めます.スタックの場合は、追加の書き込みキューが必要になる場合があります.でもQなので...

//중간보다 앞에 있으면
if (idx <= mid ) {
	for (int i = 0; i < idx; i++) {
		secondfunc(que);
		answer++;
	}
}
//중간보다 뒤에 있으면 
else {
	for (int i = idx; i <total; i++) {
		thirdfunc(que);
		answer++;
	}
}

中間の前で2番目の関数が速い場合、中間の後ろで3番目の関数が速い場合、mid変数を基準に計算し、それぞれ適切な関数に沿って進む.
まず各関数をチェックしましょう.

void secondfunc(queue<int>& que) {
	int tmp = que.front();
	que.pop();
	que.push(tmp);
}

まず やさしい 2番目 で行ないます. キューの 基本 関数であれば. インプリメンテーション 可能なら. また 説明する 必要です. いいえ. 報告する.

void thirdfunc(queue<int>& que) {
	int tmp = que.back();
	int num = que.size() - 1;
	queue<int> temp;
	temp.push(tmp);
	int front;
	for (int i = 0; i< num; i++) {
		front = que.front();
		temp.push(front);
		que.pop();
	}
	while (!que.empty()) {
		que.pop();
	}
	for (int i = 0; i < num + 1; i++) {
		front = temp.front();
		que.push(front);
		temp.pop();
	}
}

心配する3番目の関数.しかし、上でインデックスを探すときもそうですが、結果的にO(N)しか必要ないので、時間の制限を心配する必要はありません.重要なのはキューを空にする操作です.

while (!que.empty())
	que.pop();

「これを体現せずに行い、最後に残されたカウントされていない要素が生き残り、queが長くなる」「できない」という気持ちは出てこないが、今度は「それでも」という気持ちで表現しなければならない.
最後に,popは共通の進行順であるため,最初は関数として行われていたが,どうせpop()であるため,内蔵関数として実現されている.

que.pop();
out--;

最後に、out個数でwhileを続けます.