悬关

P1878 舞蹈课

#include<bits/stdc++.h>
using namespace std;
int a[200010];
int n;
struct node{
	int w,l,r;
	bool operator < (const node a)const{
		if(w == a.w) l > a.l;
		return w > a.w;
	}
}ans[200010];
priority_queue<node> q;
set<int> id;
int li[200010],cnt;
bool vis[200010];
int main(){
	cin>>n;
	for(int i = 1;i <= n;i++){
		id.insert(i);
		char op;
		cin>>op;
		if(op == 'B'){
			li[i] = 0;
		}
		else{
			li[i] = 1;
		}
	}
	id.insert(0);
	id.insert(n+1);
	for(int i = 1;i <= n;i++){
		cin>>a[i];
	}
	for(int i = 2;i <= n;i++){
		if(li[i] != li[i-1]){
		//	cout<<i<<" "<<i-1<<endl;
			q.push( node{abs(a[i]-a[i-1]),i-1,i} );
		}
	}
	vis[0] = vis[n+1] = 1;
	while(!q.empty()){
		int w = q.top().w,l = q.top().l,r = q.top().r;
		//cout<<l<<" "<<r<<endl;
		if(vis[l]){
			q.pop();
			continue;
		}
		if(vis[r]){
			q.pop();
			continue;
		}
		ans[++cnt].l = l;
		ans[cnt].r = r;
		vis[l] = 1;
		vis[r] = 1;
		id.erase(l);
		id.erase(r);
		int L = *(--id.lower_bound(l)),R = *(id.upper_bound(r));
		q.pop();
		if(li[L] != li[R]){
			if(vis[L] == 1||vis[R] == 1||L == 0||R == n+1)continue;
			q.push( node{abs(a[L]-a[R]),L,R} );
		}

	}
	cout<<cnt<<endl;
	for(int i = 1;i <= cnt;i++)cout<<ans[i].l<<" "<<ans[i].r<<endl;
}