只过样例,球跳
  • 板块P1878 舞蹈课
  • 楼主lxyzbjt_
  • 当前回复2
  • 已保存回复2
  • 发布时间2025/7/2 16:06
  • 上次更新2025/7/3 10:01:08
查看原帖
只过样例,球跳
1472033
lxyzbjt_楼主2025/7/2 16:06
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+7,INF=1e7+7;
int n,x[N],v[N],head;
char s[N];
struct bg{
	int val;
	int pos[2];
	bool operator< (const bg &B) const{
		if(val!=B.val) 
			return val>B.val;
		if(pos[0]!=B.pos[0]) 
			return pos[0]>B.pos[0];
		return pos[1]>B.pos[1];
	}
};
priority_queue<bg> DQ,eraQ;
struct node{
	int l,r;
}A[N];
void erase(int x){
	int xfrt=A[x].l,xnxt=A[x].r;
	if(x==head) head=xnxt;
	if(xfrt!=-1) A[xfrt].r=xnxt;
	if(xnxt!=-1) A[xnxt].l=xfrt;
	A[x].l=A[x].r=-1;
}
void eraser(int pos1,int pos2){
	int pos1frt=A[pos1].l,pos2nxt=A[pos2].r;
	eraQ.push(bg{abs(v[pos1]-v[pos2]),pos1,pos2});
	if(pos1frt!=-1 and x[pos1frt]^x[pos1])
		eraQ.push(bg{ abs(v[pos1frt]-v[pos1]),pos1frt,pos1});
	if(pos2nxt!=-1 and x[pos2nxt]^x[pos2])
		eraQ.push(bg{ abs(v[pos2]-v[pos2nxt]),pos2,pos2nxt});
	if(pos1frt!=-1 and pos2nxt!=-1 and x[pos1frt]^x[pos2nxt]);
		DQ.push(bg{abs(v[pos1frt]-v[pos2nxt]),pos1frt,pos2nxt});
	while(DQ.size() and eraQ.size() and
	not (DQ.top()<eraQ.top()) and not( eraQ.top()<DQ.top())){
		DQ.pop();
		eraQ.pop();
	}
	erase(pos1);
	erase(pos2);
}
vector<pair<int,int>> ans;
int main(){
	cin>>n;
	head=1;
	for(int i=1;i<=n;i++)
		A[i].l=i-1,A[i].r=i+1;
	A[1].l=-1,A[n].r=-1;
	scanf("%s",s+1);
	for(int i=1;i<=n;i++){
		x[i]=(s[i]=='G');
		cin>>v[i]; 
	}
	for(int i=1;i<n;i++){
		if(x[i]^x[i+1]==1)
			DQ.push(bg{abs(v[i]-v[i+1]),i,i+1});
	}
	while(DQ.size()){
		bg now=DQ.top();
		if(now.pos[0]==-1 or now.pos[1]==-1) break;
		ans.push_back({now.pos[0],now.pos[1]});
		eraser(now.pos[0],now.pos[1]);
	}
	cout<<ans.size()<<endl;
	for(pair<int,int> iter:ans)
		cout<<iter.first<<" "<<iter.second<<endl; 
	return 0;
}

2025/7/2 16:06
加载中...