到底哪错了,只有测试点3对了,求指出
  • 板块P1878 舞蹈课
  • 楼主czh2
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/6/30 23:12
  • 上次更新2025/7/1 18:29:17
查看原帖
到底哪错了,只有测试点3对了,求指出
1362352
czh2楼主2025/6/30 23:12
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,a[N],l[N],r[N],L[N],R[N],k=0;
char b[N];
bool vis[N];
struct node{
	int v,l,r;
	node(int x,int y,int z){
		v=x,l=y,r=z;
	}
};
bool operator <(node a,node b){
	if(a.v>b.v) return true;
	else if(a.v<b.v) return false;
	else return a.l>b.l?true:false;
}
priority_queue<node>q;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>b[i];
	cin>>a[1];
	for(int i=2;i<=n;i++){
		cin>>a[i];
		l[i]=i-1,r[i]=i+1;
		if(b[i]!=b[i-1]){
			q.push(node(abs(a[i]-a[i-1]),i-1,i));
		}
	}
	l[1]=r[n]=-1;
	while(!q.empty()){
		node t=q.top();
		q.pop();
		if(vis[t.l]==false&&vis[t.r]==false){
			vis[t.l]=vis[t.r]=true;
			L[k]=t.l,R[k++]=t.r;
			if(t.l!=1) r[l[t.l]]=r[t.r];
			if(t.r!=n) l[r[t.r]]=l[t.l];
			if(t.l!=1&&t.r!=n&&b[l[t.l]]!=b[r[t.r]]){
				q.push(node(abs(a[l[t.l]]-a[r[t.r]]),l[t.l],r[t.r]));
			}
		}
	}
	cout<<k<<endl;
	for(int i=0;i<k;i++) cout<<L[i]<<" "<<R[i]<<endl;
	return 0;
}
2025/6/30 23:12
加载中...