CE求条
  • 板块P1878 舞蹈课
  • 楼主wangshiran
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/12/17 19:44
  • 上次更新2024/12/17 22:57:32
查看原帖
CE求条
1219814
wangshiran楼主2024/12/17 19:44
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N],l[N],r[N],ans[N/2][2];
bool b[N],f[N];
struct node{
	int left,idx,cha;
}p,x;
//再写一个进队列的条件 
bool operator<(node a,node b){
	if(a.cha==b.cha) return a.idx>b.idx;
	return a.cha>b.cha;
}
priority_queue<node> pq;
int main(){
	int n;
	char c;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&c);
		if(c=='B'){
			b[i]=1;//如果是男生就标记为1 
		}
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		l[r]=i-1;
		l[i]=i+1;
		//统一向左配对
		//下标1无配对 
		if(i!=1&&b[i]!=b[i-1]){
			//开始入队
			p.idx=i,p.left=i-1,p=abs(a[i]-a[i-1]);
			pq.push(p); 
		}
	} 
	//开始在队列里找差值最小的,输出 
		int cnt=0;
		while(!pq.empty()){
		p=pq.top();
		pq.pop();
		if(f[p.left]==0&&f[p.idx]==0&&p.idx<=n&&p.left>0){
			ans[cnt][0]=p.left;
			ans[cnt++][1]=p.idx;
			f[p.left]=f[p.idx]=1; 
			//接下来要修改他们分别的前驱后继
			r[l[p.left]]=r[p.idx];
			r[l[p.idx]]=r[p.left];
			//变成一个新的链表,在找两个人入队 
			if(b[r[p.idx]]!=b[l][p.left]]){
				x.idx=r[p.idx];
				x.left=l[p.left];
				x.cha=abs(a[x.idx]-a[x.left]);
				pq.push(x);
			} 
		}
	} 
	//输出结果
	cout<<cnt<<endl;
	for(int i=0;i<cnt;i++){
		cout<<ans[i][0]<<" "<<ans[i][1]<<endl; 
	} 
	return 0;
}
2024/12/17 19:44
加载中...