社区讨论

玄关,50pts求助

P1878舞蹈课参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@m4fc1sez
此快照首次捕获于
2024/12/08 16:19
去年
此快照最后确认于
2025/11/04 13:07
4 个月前
查看原帖
求大佬帮解释一下QWQ
CPP
#include<bits/stdc++.h>

using namespace std;

struct Person{
    char xb;
    int val;
    int pre;
    int nxt;
};
Person p[200010];
struct dui{
    int l , r;
    int cha;
};
bool operator>(dui a, dui b) {
    if(a.cha != b.cha) return a.cha > b.cha;
    else return a.l > b.l;
}
dui ans[20010];
bool out[20010];
priority_queue<dui,vector<dui>,greater<dui> > h;

int main() {
    int n;
    cin >> n;
    for(int i = 1 ; i <= n ; i ++) {
        cin >> p[i].xb;
    }
    for(int i = 1 ; i <= n ; i ++) {
        cin >> p[i].val;
    }
    for(int i = 1 ; i <= n ; i ++) {
        p[i].pre = i - 1;
        p[i].nxt = i + 1;
    }
    for(int i = 1 ; i < n ; i ++) {
        if(p[i].xb != p[i + 1].xb) {
            dui t;
            t.l = i;
            t.r = i + 1;
            t.cha = abs(p[i].val-p[i + 1].val);
            h.push(t);
        }
    }
    int cnt = 0;
    while(!h.empty()) {
        dui t = h.top();
        h.pop();
        if(out[t.l] == 1 || out[t.r] == 1) continue;
        cnt ++;
        ans[cnt] = t;
        out[t.l] = 1;
        out[t.r] = 1;
        int i = p[t.l].pre;
        int j = p[t.r].nxt;
        p[i].nxt = j;
        p[j].pre = i;
        if(p[i].xb != p[j].xb && i >= 1 && j <= n) {
            dui s;
            s.l = i;
            s.r = j;
            s.cha = abs(p[i].val - p[j].val);
            h.push(s);
        }
    }
    cout << cnt << endl;
    for(int i =1 ; i <= cnt ; i ++) {
        cout << ans[i].l << " " << ans[i].r << endl;
    }
    return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...