玄关,50pts求助
  • 板块P1878 舞蹈课
  • 楼主quxiangyu
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/12/8 16:18
  • 上次更新2024/12/8 19:41:06
查看原帖
玄关,50pts求助
1241537
quxiangyu楼主2024/12/8 16:18

求大佬帮解释一下QWQ

#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;
}
2024/12/8 16:18
加载中...