求助奆佬,全WA
  • 板块P1878 舞蹈课
  • 楼主lvyou
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/9/2 21:14
  • 上次更新2023/11/4 08:07:04
查看原帖
求助奆佬,全WA
248547
lvyou楼主2021/9/2 21:14

求助奆佬,全WA

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int _next[N],_last[N],xb[N],t=0,id1[N],value[N];
bool book[N];
struct node{
	int lid,rid;
}a[N];
int n;
struct comp{
	bool operator()(const node x,const node y)
	{
		if(abs(value[x.lid]-value[x.rid])!=abs(value[y.lid]-value[y.rid]))
		return abs(value[x.lid]-value[x.rid])>abs(value[y.lid]-value[y.rid]);
		return x.lid>y.lid;
	}
};
priority_queue<node,vector<node>,comp>q;
void init()
{
	cin>>n;
	char c;
	for(int i=1;i<=n;i++)
	{
		cin>>c;
		if(c=='G')
		xb[i]=1;
		_next[i]=i+1;
		_last[i]=i-1;
		a[i].lid=i-1;
		a[i].rid=i;
		//cout<<c<<endl;
	}
	xb[0]=xb[n+1]=2;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&value[i]);
	}
}
node make_edge(int x,int y)
{
	node xx;
	xx.lid=x;
	xx.rid=y;
	return xx;
}
node x;
void work()
{
	for(int i=2;i<=n;i++)
	{
		if(xb[i]+xb[i-1]==1)
		{
			//cout<<"bb"<<a[i].lid<<" "<<a[i].rid<<endl;
			q.push(a[i]);
		}
	}
	/*while(!q.empty())
	{
		cout<<q.top().lid<<" "<<q.top().rid<<endl;
		q.pop();
	}*/
	while(!q.empty())
	{
		x=q.top();
		q.pop();
		//cout<<x.lid<<" "<<x.rid<<endl;
		if((!book[x.lid])&&(!book[x.rid]))
		{
			//cout<<"xx";
		//	cout<<x.lid<<" "<<x.rid<<endl;
			book[x.lid]=1;
			book[x.rid]=1;
			id1[++t]=x.lid;
			_last[_next[x.rid]]=_last[x.lid];
			_next[_last[x.lid]]=_next[x.rid];
			//cout<<"xxx"<<_last[x.lid]<<" "<<_next[x.rid]<<endl;
			if(xb[_next[x.rid]]+xb[_last[x.lid]]==1)
			{
				//cout<<"a"<<_last[x.lid]<<" "<<_next[x.rid]<<endl;
				q.push(make_edge(_last[x.lid],_next[x.rid]));
			}
		}
		//system("pause");
	}
	printf("%d\n",t);
	for(int i=1;i<=t;i++)
	{
		printf("%d %d\n",id1[i],_next[id1[i]]);
	}
	return;
}
int main()
{
	ios::sync_with_stdio(0);
	init();
	work();
	return 0;
}

求大佬指教

2021/9/2 21:14
加载中...