WA,70分求助QWQ
查看原帖
WA,70分求助QWQ
467443
A宋锦瑞A楼主2023/8/4 22:40
#include<bits/stdc++.h>

using namespace std;

const int N=2e5+10;

struct node {
	int v,l,r;
	node(int iv,int il,int ir) {
		v=iv,l=il,r=ir;
	}
	bool operator<(const node &a) const {
		if(v!=a.v) {
			return v>a.v;
		} else {
			return l>a.l;
		}
	}
};

int n;
int b,g;
char s[N];
int v[N];
priority_queue<node>q;
int sum;
bool u[N];

int main() {
	ios::sync_with_stdio(false);
	scanf("%d",&n);
	scanf("%s",s+1);
	for(int i=1; i<=n; i++) {
		if(s[i]=='B') {
			b++;
		} else if(s[i]=='G') {
			g++;
		}
		scanf("%d",&v[i]);
		if(i!=0&&s[i]!=s[i-1]) {
			q.push(node(abs(v[i]-v[i-1]),i-1,i));
		}
	}
	sum=min(b,g);
	cout<<sum<<'\n';
	while(sum&&q.size()) {
		int l=q.top().l;
		int r=q.top().r;
		q.pop();
		if(!u[l]&&!u[r]) {
			cout<<l<<" "<<r<<'\n';
			u[l]=u[r]=1;
			while(l>0&&u[l]) {
				l--;
			}
			while(r<=n&&u[r]) {
				r++;
			}
			if(l>0&&r<=n&&s[l]!=s[r]) {
				q.push(node(abs(v[l]-v[r]),l,r));
			}
			sum--;
		}
	}

	return 0;
}
2023/8/4 22:40
加载中...