50pts求调
查看原帖
50pts求调
470299
fang20081114楼主2024/8/18 16:15
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
string s; 
int n,a[N];
char c[N];
bool vis[N];
int k=0;
struct node{
	int delta,lnum,bnum,l,r;
	bool operator < (const node &x) const{
		return delta>x.delta  ;
	}
};
priority_queue<node> ans;
queue<pair<int,int> > aans;
inline int read(){
	char c=getchar();
	int x=0,f=1;
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
int main(){
//	freopen("dancinglessons.in","r",stdin);
//	freopen("dancinglessons.out","w",stdout);
	n=read();
	cin>>s;
	c[0]=-10;
	for(int i=1;i<=n;i++){
		if(s[i-1]=='B') c[i]=1;
		else c[i]=-1;
	}
	for(int i=1;i<=n;i++){
		a[i]=read();
		if(-c[i]==c[i-1]){
			if(a[i]>=a[i-1]) ans.push((node){a[i]-a[i-1],a[i-1],a[i],i-1,i});
			else ans.push((node){a[i-1]-a[i],a[i],a[i-1],i-1,i});
		}
	}
	while(!ans.empty()){
		node t=ans.top();
		ans.pop();
		if(!vis[t.l]&&!vis[t.r]&&-c[t.l]==c[t.r]){
			aans.push((pair<int,int>){t.l,t.r});
		//	cout<<"||"<<t.delta<<"-|"<<t.l<<" "<<t.r<<"|"<<t.lnum<<" "<<t.bnum<<endl;
			vis[t.l]=vis[t.r]=true;
			int i=t.l-1;
			while(vis[i]&&i>=1) i--;
			if(i<1) continue;
			int j=t.r+1;
			while(vis[j]&&j<=n) j++;
			if(j>n) continue;
			if(a[i]>=a[j]) ans.push((node){a[i]-a[j],a[j],a[i],i,j});
			else ans.push((node){a[j]-a[i],a[i],a[j],i,j});
		}
	}
	cout<<aans.size()<<endl;
	while(!aans.empty()){
		cout<<aans.front().first<<" "<<aans.front().second<<endl;
		aans.pop();
	}
	return 0;
}
/*
5
BGBGG
3 6 5 1 4
*/
2024/8/18 16:15
加载中...