栈，优先级队列，map，set

文章目录 栈题目解析代码 优先级队列题解代码 map题解代码 set题解代码

栈

题目解析

1.先把元素push进栈中，如果栈非空并且栈中的元素按顺序和k相等就出栈，直到栈为空或者k != sk.top()

代码 #include<iostream> #include<stack> #include<vector> using namespace std; int main() { stack<int> sk; int n = 0; cin >> n; vector<int> v(n); for (int i = 0; i < n; i++) cin >> v[i]; int k = 1; for (int i = 0; i < n; i++) { sk.push(v[i]); while(!sk.empty()&&k == sk.top()) { sk.pop(); k++; } } if (sk.empty()) { cout << "Yes" << '\n'; } else { cout << "No" << '\n'; } return 0; } 优先级队列

题解

1. 用sum统计篮子的重量 2. 是1就push,增加sum 3. 是2就减少sum,pop,并且要判空，非空才能减，不然优先级对列会报错

代码 #include<iostream> #include<stack> #include<vector> #include<queue> using namespace std; const int N = 1e5 + 10; using ll = long long; int main() { int q; cin >> q; priority_queue<ll> pq; ll sum = 0; while(q--) { int x = 0; cin >> x; if(x == 1) { int y; cin >> y; pq.push(y); sum += y; } else if( x == 2) { if(!pq.empty()) { sum -= pq.top(); pq.pop(); } } } cout << sum; return 0; } map

题解

1. map统计字符串出现的次数 2. vector可以把字符串按顺序输出 3. 第一次出现就插入到vector中

代码 #include<iostream> #include<vector> #include<map> #include<string> using namespace std; const int N = 1e5 + 10; using ll = long long; void slove() { int n; cin >> n; map<string,int> p; // map是有序的 vector<string> v; // 表示字符串出现的顺序 for(int i = 0;i < n;i++) { string s; cin >> s; if(p.count(s)) p[s]++; else { v.push_back(s); p[s] = 1; } } for(auto& x : v) cout << x << " " << p[x] << '\n'; } int main() { int t = 0; cin >> t; while(t--) slove(); return 0; } set

题解

1. 把数插入到set中，set会自动帮我们排好序的，然后输出就行了

代码 #include<iostream> #include<vector> #include<set> #include<algorithm> using namespace std; int main() { int n; cin >> n; set<int> st; for(int i = 0;i < n;i++) { int x; cin >> x; st.insert(x); } for(auto x : st) cout << x << " "; return 0; }