社区讨论

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 条回复,欢迎继续交流。

正在加载回复...