只过#11 求助 样例过
查看原帖
只过#11 求助 样例过
738306
chasing_dream楼主2025/8/4 23:34
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}
const int maxn=2e5+10;
int n;
string s;
struct node{
	int w,c,d;//差值 左 右
	bool operator<(const node &t) const{
		if(w==t.w) return c>t.c;
		else return w>t.w;
	}
};
priority_queue<node> q;
bool flag[maxn];
int a[maxn],l[maxn],r[maxn];//l r为链表
int ans1[maxn],ans2[maxn],cnt;
int main()
{
	n=read();
	cin>>s;
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<n;i++)
	{
		if(s[i-1]!=s[i]) q.push((node){abs(a[i+1]-a[i]),i,i+1});
	}
    s+='H';
	for(int i=1;i<=n;i++) l[i]=i-1,r[i]=i+1;
	while(!q.empty())
	{
		node t=q.top();
		q.pop();
		int x=t.c,y=t.d,w=t.w;
		if(flag[x] || flag[y]) continue;
		r[l[x]]=r[x];
		l[r[y]]=l[x];
		cnt++;
		ans1[cnt]=x,ans2[cnt]=y;
		flag[x]=1,flag[y]=1;
		if(!flag[l[x]] && !flag[r[y]])
			if((s[l[x]-1]+s[r[x]-1])==('G'+'B')) 
				q.push((node){abs(a[l[x]]-a[r[x]]),l[x],r[x]});
	}
	cout<<cnt<<endl;
	for(int i=1;i<=cnt;i++) cout<<ans1[i]<<' '<<ans2[i]<<endl;
	return 0;
}


2025/8/4 23:34
加载中...