【玄关】50pts求调,不是副关键词问题
查看原帖
【玄关】50pts求调,不是副关键词问题
655185
Nullity_Silence楼主2024/8/27 23:30

rt

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>

using namespace std;

const int N=2e5+10;

struct node
{
	int val,l,r;
};

int n,tot;
string str;
int value[N],res1[N],res2[N],pre[N],nxt[N];
bool st[N];
priority_queue<node,vector<node>,greater<node>> q;

bool operator<(node a,node b)
{
	if(a.val==b.val)
		return a.l>b.l;
	return a.val<b.val;
}

bool operator>(node a,node b)
{
	if(a.val==b.val)
		return a.l<b.l;
	return a.val>b.val;
}

int main()
{
	cin>>n>>str;
	for(int i=1;i<=n;i++)
		cin>>value[i];
	for(int i=0;i<str.size()-1;i++)
		if(str[i]!=str[i+1])
			q.push((node){abs(value[i+1]-value[i+2]),i+1,i+2});
	for(int i=1;i<=n;i++)
	{
		pre[i]=i-1;
		nxt[i]=i+1;
	}
	st[0]=1;
	st[n+1]=1;
	while(!q.empty())
	{
		node t=q.top();
		q.pop();
		if(st[t.l]||st[t.r])
			continue;
		nxt[pre[t.l]]=nxt[t.r];
		pre[nxt[t.r]]=pre[t.l];
		res1[++tot]=t.l;
		res2[tot]=t.r;
		st[t.l]=1;
		st[t.r]=1;
		if(st[pre[t.l]]||st[nxt[t.r]])
			continue;
		if(str[pre[t.l]-1]==str[nxt[t.r]-1]
			continue;
		q.push({abs(value[pre[t.l]]-value[nxt[t.r]]),pre[t.l],nxt[t.r]});
	}
	cout<<tot<<endl;
	for(int i=1;i<=tot;i++)
		cout<<res1[i]<<' '<<res2[i]<<endl;
	return 0;
}
2024/8/27 23:30
加载中...