CFR-679D Shurikens 题解

题目大意

你经营这一个商店，商店中有1~n，n个物品，给你一个账单 ，加代表你放了一个货在货架上，减代表

你卖出当前货架上序号最小的物品，并且告诉你他的序号，问这个账单是否成立，成立则输出任何一个上货的顺序。

解题思路

这场简直有毒，D题比C题容易多了。

说实话，这题很有意思。

首先，你正着来模拟很麻烦，不好模拟。

于是可以倒过来模拟，减就是入栈，加就是出栈，每次输出栈顶，维护栈中最小值即可。

完整代码

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

vector<string>v;
stack<int> st, ans;

int main() {
	int n; cin >> n;
	int cnt0, cnt1;
	cnt0 = cnt1 = 0;
	string s;
	getchar();
	while (cnt0 != n || cnt1 != n) {
		getline(cin, s);
		if (s[0] == '+')	cnt0++;
		else cnt1++;
		v.push_back(s);
	}
	int m = 1e9, flag = 1;
	for (int i = v.size() - 1; i >= 0; i--) {
		if (v[i][0] == '-') {
			string t;
			for (int j = 2; j < v[i].length(); j++) t += v[i][j];
			st.push(stoi(t)), m = min(m, stoi(t));
		}
		else {
			if (st.empty()) {
				flag = 0; break;
			}
			int t = st.top(); st.pop();
			ans.push(t);
			if (!st.empty())	m = st.top();
			else m = 1e9;
		}
		if (!st.empty()&&m != st.top()) {
			flag = 0; break;
		}
	}
	if (flag) {
		cout << "YES" << endl;
		while (!ans.empty()) {
			int t = ans.top(); ans.pop();
			cout << t << ' ';
		}
		cout << endl;
	}
	else cout << "NO" << endl;

}