社区讨论
玄关,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 条回复,欢迎继续交流。
正在加载回复...