AcWing116
A AcWing 5134. 简单判断
void solve() {
int x, y, z;
cin >> x >> y >> z;
if(x > y + z)cout << '+' << endl;
else if(y > x + z)cout << '-' << endl;
else if(x == y && z == 0)cout << '0' << endl;
else cout << '?' << endl;
}
B AcWing 5135. 奶牛用餐
题意：每头奶牛按照规定的规则用餐，同一时刻可共存\(k\)头奶牛，输出每头奶牛用餐结束的时间
规则：1.每头奶牛都必须由约翰安排座位用餐。
2.每头奶牛从到达食堂的那一刻起，即刻进入待安排状态。
3.任意时刻，只要存在空座位以及待安排奶牛，约翰就会即刻安排奶牛就座用餐。
4.如果某一时刻，空座位的数量少于待安排奶牛的数量，则优先安排编号更小的奶牛就座用餐。每头奶牛用餐完毕的那一时刻都会 被约翰立即轰走。
思路：先把最初的\(k\)头奶牛放入优先对列（小根堆），再去遍历剩下的\(n-k\)头奶牛，每次取最早结束的奶牛，也就是堆顶，把新的奶牛放进堆里，并且同步输出答案
void solve() {
int n, k;
cin >> n >> k;
vector<PII> a(n);
priority_queue<int, vector<int>, greater<int>> pq;
for(auto &[x, y] : a)cin >> x >> y;
for(int i = 0; i < min(n, k); i++) {
cout<<a[i].fi+a[i].se<<endl;
pq.push(a[i].fi + a[i].se);
}
for(int i = k; i < n; i++) {
auto t = pq.top();
pq.pop();
// cout << t << endl;
pq.push(max(t, a[i].fi) + a[i].se);
cout<<max(t, a[i].fi) + a[i].se<<endl;
}
}
C AcWing 5136. 平衡括号字符串
**题意：给定一个字符串 \(s\)，该字符串的每个字符都是 (、) 或 # 之一。 你的任务是将 \(s\) 中的每个 # 变换为一个或多个 )，从而得到一个平衡括号字符串。 不同 # 变换的 ) 的数量可以不同。 请你输出为了满足条件，每个 # 所需变换的 ) 的数量。 如果方案不唯一，则输出任意合理方案均可。 **
当一个字符串满足以下所有条件时，该字符串被称为平衡括号字符串： 字符串仅由 ( 和 ) 组成。 字符串所包含的 ( 和 ) 的数量相同。 对于字符串的任意前缀，其所包含的 ( 的数量都不少于 ) 的数量
思路：先找无解的情况，就是前缀(的数量小于#和)的数量之和，最后一个#之后字符串的后缀缀(的数量大于)的数量，以及最后一个#之后的字符串左右括号数量相等，但是无法相互抵消，这使用一个栈来判断，误解之后有解的情况直接前\(k-1\)输出\(1\)，剩下的数量在最后一个#的地方输出即可
void solve() {
string s;
cin >> s;
int l = 0, r = 0, x = 0;
int ss = 0;
for(auto i : s) {
if(i == '#')ss++;
if(i == '(')l++;
else r++;
if(l < r) {
cout << -1 << endl;
return ;
}
// cout << l << ' ' << r << endl;
}
int pos = 0;
for(int i = 0; i < s.size(); i++) {
if(s[i] == '#')pos = max(i, pos);
}
int sl = 0, sr = 0;
bool ok = true;
for(int i = s.size() - 1; i >= pos + 1; i--) {
if(s[i] == '(')sl++;
else sr++;
if(sl > sr) ok = false;
}
if(!ok) {
cout << -1 << endl;
return ;
}
stack <char> stk;
if(sl == sr) {
for(int i = pos + 1; i < s.size(); i++) {
if(s[i] == '(')stk.push(i);
else if(stk.size())stk.pop();
}
}
if(stk.size()) {
cout << -1 << endl;
return ;
}
for(int i = 0; i < ss - 1; i++)cout << 1 << endl;
cout << l - r - (x - 1) << endl;
}