C++每日刷题day2025.7.10

思路就是遇到数字就push进栈，遇到符号就取栈顶俩元素进行对应符号运算再push进栈中，直到栈中只剩一个数字。

class Solution {
public:bool isNumber(string& x){if (x == "+" || x == "-" || x == "*" || x == "/")return false;else return true;}int evalRPN(vector<string>& tokens) {stack<int> st;for (int i = 0; i < tokens.size(); ++i){string& x = tokens[i];if (isNumber(x)) st.push(atoi(x.c_str()));else{int num1 = st.top();st.pop();int num2 = st.top();st.pop();switch (x[0]){case '+' :{st.push(num1 + num2);break;}case '-' :{st.push(num2 - num1);break;}case '*' :{st.push(num1 * num2);break;}case '/' :{st.push(num2 / num1);break;}default:break;}}}return st.top();}
};

来个辅助栈，一个正常的栈，另一个是只存放最小值的栈。

class MinStack {
public:stack<int> st;stack<int> min_st;MinStack() {min_st.push(INT_MAX);}void push(int val) {st.push(val);min_st.push(min(val, min_st.top()));}void pop() {st.pop();min_st.pop();}int top() {return st.top();}int getMin() {return min_st.top();}
};/*** Your MinStack object will be instantiated and called as such:* MinStack* obj = new MinStack();* obj->push(val);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->getMin();*/

我是用了一个堆一个优先级队列，优先级队列用来存放偶数的，栈用来存放奇数的，每次只需要取优先级队列/2再判断是不是偶数即可。

#include <iostream>
#include <stack>
#include <queue>
#include <vector>
using namespace std;int main() {long long n, k;cin >> n >> k;// 使用 vector 动态分配内存vector<long long> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}priority_queue<long long> st;stack<long long> other;for (long long i = 0; i < n; i++) {if (a[i] % 2 == 0) {st.push(a[i]);} else {other.push(a[i]);}}while (st.size() && k--) {long long top = st.top();st.pop();top /= 2;if (top % 2 == 0) st.push(top);else other.push(top);}long long sum = 0;while (!st.empty()) {sum += st.top();st.pop();}while (!other.empty()) {sum += other.top();other.pop();}cout << sum;return 0;
}