0pts,不知道错哪了
  • 板块P1878 舞蹈课
  • 楼主hwc2011
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/8/11 15:27
  • 上次更新2024/8/11 15:47:27
查看原帖
0pts,不知道错哪了
1313003
hwc2011楼主2024/8/11 15:27
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[200005],l[200005],r[200005],p[200005],sum;
char s[200005];
struct Node{
	int cnt,x,y;
	friend bool operator < (Node a,Node b){
		return a.cnt<b.cnt;
	}
}ans[100005];
priority_queue<Node>q;
signed main(){
	scanf("%lld%s",&n,s+1);
	for(int i=1;i<=n;i++) scanf("%lld",a+i);
	for(int i=2;i<=n;i++){
		if(s[i]^s[i-1]) q.push({abs(a[i]-a[i-1]),i-1,i});
	}
	for(int i=2;i<n;i++){
		r[i-1]=l[i+1]=i;
	}
	while(!q.empty()){
		int x=q.top().x,y=q.top().y;
		q.pop();
		if((!p[x])&&(!p[y])){
			p[x]=p[y]=1;
			ans[++sum]={0,x,y};
			l[r[y]]=l[x];
			r[l[x]]=r[y];
			int left=l[r[y]],right=r[l[x]];
			if((!p[left])&&(!p[right])&&left>0&&right>0&&s[left]^s[right]) q.push({abs(a[right]-a[left]),left,right});
		}
	}
	printf("%lld\n",sum);
	for(int i=1;i<=sum;i++){
		printf("%lld %lld\n",ans[i].x,ans[i].y); 
	}
}
2024/8/11 15:27
加载中...