社区讨论
50分求助
P1878舞蹈课参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lo3f46of
- 此快照首次捕获于
- 2023/10/24 05:36 2 年前
- 此快照最后确认于
- 2023/10/24 05:36 2 年前
CPP
#include<bits/stdc++.h>
using namespace std;
int n,d[100005],num[100005],ans[100005][5],t;
string s;
struct node{
int i,j,diff;
bool operator <(const node &b)const{ //重置小于符
if(diff>b.diff) return true;
if(diff<b.diff) return false;
return i>b.i;
}
};
priority_queue<node> q;
int main(){
int l,r;
cin>>n>>s;
s='0'+s;
for(int i=1;i<=n;i++){
cin>>num[i];
}
for(int i=1;i<n;i++){
if(s[i]!=s[i+1]){
q.push({i,i+1,abs(num[i]-num[i+1])});
}
}
while(!q.empty()){
node c=q.top();
q.pop();
l=c.i;
r=c.j;
if(d[l]==1||d[r]==1){
continue;
}
ans[t][0]=l;ans[t][1]=r;
t++;
d[l]=1;
d[r]=1;
while(l>0&&d[l]==1){
l--;
}
if(l==0){
continue;
}
while(r<=n&&d[r]==1){
r++;
}
if(r>n){
continue;
}
if(s[l]==s[r]){
continue;
}
q.push({l,r,abs(num[l]-num[r])});
}
cout<<t<<endl;
for(int i=0;i<t;i++){
cout<<ans[i][0]<<' '<<ans[i][1]<<endl;
}
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...