求助
查看原帖
求助
1020531
liuyiyang_khaili楼主2024/1/25 11:05
#include<bits/stdc++.h>
using namespace std;
struct node {
    int b;
    int g;
    int val;
    node(int _b, int _g, int _val) : b(_b), g(_g), val(_val) {}

    bool operator<(const node& a) const {
        return val > a.val;
    }
};
const int N = 2e5 + 7;
int ans[N][3], cnt = 0;
bool st[N];
int n;
string bg;
priority_queue<node> g;
int a[N];
int l[N + 1], r[N + 1];
void makans(int b, int g) {
    cnt++;
    ans[cnt][1] = b;
    ans[cnt][2] = g;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    cin >> bg;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        l[i] = i == 1 ? 0 : i - 1; 
        r[i] = i == n ? 0 : i + 1;
    }

    for (int i = 1; i < n; i++) {
        if (bg[i - 1] != bg[i]) {//字符串下标从0开始,所以要-1
            node t(i, i + 1, abs(a[i] - a[i + 1]));
            g.push(t);
        }
    }
    while (!g.empty()) {
        int u = g.top().b, v = g.top().g;
        if (st[u] || st[v]) {
            g.pop();
            continue;
        }
        makans(u, v);
        g.pop();
        st[u] = 1;
        st[v] = 1;
        int p = l[u], q = r[v];
        if (p > 0 && q > 0) {
            r[p] = q;
            l[q] = p;
        }
        else if (p > 0) {
            r[p] = 0;
        }
        else if (q > 0) {
            l[q] = 0;
        }
        else {
            break;
        }
        if (q > 0 && p > 0 && bg[p - 1] == bg[q - 1]) {
            continue;
        }
        node newNode(p, q, abs(a[p] - a[q]));
        g.push(newNode);
    }

    cout << cnt << '\n';
    for (int i = 1; i <= cnt; i++) {
        cout << ans[i][1] << ' ' << ans[i][2] << '\n';
    }
    return 0;
}
2024/1/25 11:05
加载中...