0pts求调
查看原帖
0pts求调
1183074
xzy_AK_IOI楼主2024/8/3 16:59
/*
I AK IOI/NOI/CTSC/THUPC/WC/ACM/ICPC/CSP/NOIP/APIO
*/
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct node{
	int cha;
	int start;
	int end;
	bool operator < (const node& a) const{
		if (a.cha!=this->cha){
			return a.cha<this->cha;
		}
		return a.start<this->start;
	}
};
priority_queue <node> Q;
int n;
struct MAN{
	int a;
	int b;
}man[N];
int ans=0;
struct student{
	int id;
	char x;
	int score;
	int next;
	int last;
}stu[N];//双向链表
int cnt,tail,head;
void pop(int x){//删除x及x后元素
	stu[stu[x].last].next=stu[stu[x].next].next;
	stu[stu[stu[x].next].next].last=stu[x].last;
}
void l_pop(){//删除1及2
	int g=tail;
	tail=stu[stu[tail].next].next;
	stu[stu[stu[g].next].next].last=N-10;
}
void r_pop(){//删除表尾及前一项
	int g=head;
	head=stu[stu[head].last].last;
	stu[stu[stu[g].last].last].next=N-10;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;							
	for (int i=1;i<=n;i++){
		cin>>stu[i].x;
		stu[i].id=i;
	}
	for (int i=1;i<=n;i++){
		cin>>stu[i].score;
		stu[i].next=i+1;
		stu[i].last=i-1;
	}
	stu[n].next=N-10;stu[1].last=N-10;
	cnt=n;tail=1,head=n;
	while (true){
		bool _B=0,_G=0;int leng=0;
		for (int i=tail;i!=N-10;i=stu[i].next){
			leng++;
			if (stu[i].x=='B') _B=1;
			if (stu[i].x=='G') _G=1;
		}
		if (!_B || !_G || leng<=1) break;
		for (int i=tail;i!=head;){
			if (stu[i].x!=stu[stu[i].next].x){
				if (i==tail && i==stu[head].last){
					Q.push((node){abs(stu[i].score-stu[stu[i].next].score),stu[i].id,stu[stu[i].next].id});
					tail=N-10;
					break;
				}
				if (i==tail && i!=stu[head].last){
					Q.push((node){abs(stu[i].score-stu[stu[i].next].score),stu[i].id,stu[stu[i].next].id});
					i=stu[stu[i].next].next;
					l_pop();
				}
				else if (i==stu[head].last){
					Q.push((node){abs(stu[i].score-stu[stu[i].next].score),stu[i].id,stu[stu[i].next].id});
					r_pop();
					break;
				}
				else{
					Q.push((node){abs(stu[i].score-stu[stu[i].next].score),stu[i].id,stu[stu[i].next].id});
					int y=i;
					i=stu[stu[i].next].next;
					pop(y);	
				}
			}
			else{
				i=stu[i].next;
			}
		}
		while (Q.size()){
			ans++;
			man[ans].a=Q.top().start;
			man[ans].b=Q.top().end;
			Q.pop();
		}
	}
	cout<<ans<<'\n';
	for (int i=1;i<=ans;i++){
		cout<<man[i].a<<" "<<man[i].b<<'\n';
	}
	return 0;
}
/*
4
BGBG
4 2 4 3
4
BBGG
4 6 1 5
4
BGBB
1 1 2 3
6
BGBGBG
1 2 1 2 3 3
*/

样例过

2024/8/3 16:59
加载中...