求助!!!!!
查看原帖
求助!!!!!
140411
yangzhiqin楼主2020/10/16 20:58
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
struct node
{
	int l,r,c;
}a[200010];
typedef pair<int,int>pll;
priority_queue<pll,vector<pll>,greater<pll> >q;
char s[200010];
bool f[200010];
pll dn[100010];
void del(int now)
{
	a[a[a[now].l].l].r=a[now].r;
	a[a[now].r].l=a[a[now].l].l;
}
int main()
{
	int n;scanf("%d%s",&n,s+1);
	scanf("%d",&a[1].c);a[1].l=0,a[1].r=2;
	for(int i=2;i<=n;i++)
	{
		scanf("%d",&a[i].c);
		a[i].l=i-1,a[i].r=i+1;
		if(s[i]!=s[i-1])q.push({abs(a[i].c-a[i-1].c),i});
	}
	int m=0;
	memset(f,true,sizeof(f));
	f[0]=f[n+1]=false; 
	while(!q.empty())
	{
		pll t=q.top();q.pop();
		if(!f[t.second]||!f[a[t.second].l]||s[t.second]==s[a[t.second].l])continue;
		if(s[a[t.second-1].l]!=s[a[t.second].r]&&a[t.second-1].l>=1&&a[t.second].r<=n)
		{
			int dt=abs(a[a[t.second-1].l].c-a[a[t.second].r].c);
			q.push({dt,a[t.second].r}); 
		}
		dn[++m].first=t.second,dn[m].second=a[t.second].l;
		f[t.second]=f[a[t.second].l]=false;
		del(t.second);
	}
	printf("%d\n",m);
	for(int i=1;i<=m;i++)printf("%d %d\n",dn[i].second,dn[i].first);
	return 0;
}
/*
5
BGGBB
5 1 2 2 3

5
BGGBG
4 2 2 3 4

*/
2020/10/16 20:58
加载中...