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;
}