大学連合アルゴリズムウィンター学院第6回(スタック、キュー、インデックス)

52211 ワード

スタック


LIFO構造
後で入って初めて出てきます
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;

int ans, i, j, n, m;

int main(void) {
	freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	//cout.tie(nullptr);
	cout << fixed;
	cout.precision(2);

	ll n = 0;
	cin >> n;
	string s;
	cin >> s;
	vector<double> a(n);
	for (i = 0; i < n; ++i) {
		cin >> a[i];
	}
	stack<double> st;

	for (i = 0; i < s.length(); ++i) {
		if (s[i] == '*' || s[i] == '/' || s[i] == '+' || s[i] == '-') {
			double a = st.top();
			st.pop();
			double b = st.top();
			st.pop();

			if (s[i] == '*') {
				st.push((1.0) * a * b );
			}
			else if (s[i] == '/') {
				st.push((1.0) * b / a);
			}
			else if (s[i] == '+') {
				st.push(a + b);
			}
			else if (s[i] == '-') {
				st.push(b - a);
			}
		}
		else {
			st.push(a[s[i] - 'A']);
		}
	}
	//printf("%.2f\n", st.top());
	cout << st.top();

}

キュー


FIFO(First In First Out)

1158ジョセフス問題

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, k;
	cin >> n >> k;
	queue<int> q;
	for (int i = 1; i <= n; ++i) {
		q.push(i);
	}

	int t = 0;
	cout << '<';
	while (!q.empty()) {
		t++;
		int temp = q.front();
		q.pop();
		if (t % k == 0) {
			cout << temp;
			if (!q.empty()) cout << ", ";
		}
		else q.push(temp);
	}
	cout << '>';
}

19591ユニークコンピューティング

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;

int ans, i, j, n, m;
int main(void) {
	freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cout.tie(nullptr);
	//cin.tie(nullptr);

	string s;
	getline(cin, s);
	
	
	bool flag = false;
	while (s != ".") {
		//cout << s << '\n';
		flag = true;
		stack<char> so;
		for (i = 0; i < s.length(); ++i) {
			if (s[i] == '(' || s[i]=='[') {
				so.push(s[i]);
			}
			else if (s[i] == ')') {
				if (!so.empty() and so.top() == '(') so.pop();
				else { cout << "no" << '\n'; flag = false; break; }
			} else if(s[i] == ']') {
				if (!so.empty() and so.top() == '[') so.pop();
				else { cout << "no" << '\n'; flag = false; break; }
			}
		}

		if ((!so.empty()) and flag) {
			cout << "no" << '\n';
			while (!so.empty()) so.pop();
		}
		else if(flag){
			cout << "yes" << '\n';
		}
		getline(cin, s);
		//cin.ignore();
	}
}

1966プリンタキュー


キューと優先キューの使用
数字でrankをあげて、探し続けます.
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;

int ans, i, j, n, m;
int main(void) {
	freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);
	int t;
	cin >> t;
	
	while (t--) {
		int n, m;
		cin >> n >> m;
		int rank;
		vector<pair<int, int>> a;
		queue<pair<int, int>> q;
		priority_queue<int> pq;
		for (i = 0; i < n; ++i) {
			cin >> rank;
			q.push(make_pair(i,rank));
			pq.push(rank);
		}
		int c = 1;
		while (!q.empty()) {
			int num = q.front().first;
			int rank = q.front().second;
			q.pop();
			if (rank == pq.top()) {
				if (num == m) {
					cout << c << '\n';
					break;
				}
				else {
					c += 1;
					pq.pop();
				}
			}
			else {
				q.push(make_pair(num, rank));
			}
		}
	}
}

デッキ


1021回転キュー

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;

int ans, i, j, n, m;
int main(void) {
	freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);
	int n, m;
	cin >> n >> m;
	deque<int> dq;
	for (i = 1; i <= n; ++i) {
		dq.push_back(i);
	}
	vector<int> a;
	for (i = 0; i < m; ++i) {
		int temp;
		cin >> temp;
		a.push_back(temp);
	}
	int ans = 0;
	int c = 0;
	for (i = 0; i < a.size(); ++i) {
		int index = 0;
		for (j = 0; j < dq.size(); ++j) {
			if (a[i] == dq[j]) {
				index = j;
				break;
			}
		}
		c = 0;
		/* 뒤에서 빼기*/
		if (index > dq.size() - index) {
			while (1) {
				if (dq.front() == a[i]) {
					dq.pop_front();
					break;
				}
				else {
					dq.push_front(dq.back());
					dq.pop_back();
					ans += 1;
				}
			}
		}
		else {
			while (1) {
				if (dq.front() == a[i]) {
					dq.pop_front();
					break;
				}
				else {
					dq.push_back(dq.front());
					dq.pop_front();
					ans += 1;
				}
			}
		}
	}
	cout << ans << '\n';
}