社区讨论

求助

P1878舞蹈课参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lrbhkutl
此快照首次捕获于
2024/01/13 11:07
2 年前
此快照最后确认于
2024/01/13 14:13
2 年前
查看原帖
本蒟蒻看题解看半天打问号的那里没看懂而且代码也错了
CPP
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
const int N =200005; 
struct Node{
	int minus;
	int l, r;
	char ch;
	int p;
}a[N];
priority_queue<Node> q;
int ans[N][2];
bool operator<(Node x, Node y){//对技术差值排序 
	if(x.minus == y.minus)
		return x.p < y.p;
	return x.minus < y.minus;
}
int main(){
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		cin >> a[i].ch;
	int now, len = 0;
	scanf("%d", &now);
	for(int i = 1; i < n; i++){
		int x;
		scanf("%d", &x);
		a[i].p = i;
		a[i].minus = abs(now-x);//将差值放入当前位 
		a[i].l = i-1;
		a[i].r = i+1;
		q.push(a[i]);		
		now = x;
	}
	a[n].r = n+1, a[n].p = n, a[n].minus = 1e9; //最后一位没差值设最大
	while(!q.empty()){
		int x = q.top().p, k = q.top().minus;//当前位 
		q.pop();
		int y = a[x].r;//当前后一位
		if(a[x].minus == k && a[x].ch != a[y].ch && (y != n+1) && (x >= 1)){//若配对 
			ans[++len][0] = x, ans[len][1] = y;
			a[a[x].l].minus += a[x].minus + a[y].minus;//更新此时差?? 
			a[a[y].r].l = a[x].l;a[a[x].l].r = a[y].r;//重连 
			if(a[x].l > 0 && a[y].r < n)
				q.push(a[a[x].l]);
			a[x].l = a[x].r = 0, a[y].l = a[y].r = n+1;//断 
		} 
	} 
	printf("%d\n", len);
	for(int i = 1; i <= len; i++)
		printf("%d %d\n", ans[i][0], ans[i][1]);
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...