【新春不断更】题海拾贝：P1878 舞蹈课

         Hello大家好！很高兴我们又见面啦！给生活添点passion，开始今天的编程之路！

我的博客：<但凡.

我的专栏：《编程之路》、《数据结构与算法之美》、《题海拾贝》

欢迎点赞，关注！

 1、题目

题目链接：舞蹈课 - 洛谷 

2、题解

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<queue>
#include<cmath>
typedef long long LL;
using namespace std;
const int N = 2e5 + 10;
//双向链表存放每个人的技术
int e[N];
int pre[N], ne[N];//存放左右人的下标
//定义堆中存放的node
struct node
{
	int num;//技术差
	int i, j;//这一对人的下标
	//定义比较方式，运算符重载
	bool operator <(const node& n) const
	{
		//技术差最小的先出，技术差相等则最左边的先出
		//小根堆
		if (num != n.num) return num > n.num;
		else if (i != n.i) return i > n.i;
		else return j > n.j;
	}
};
priority_queue<node> heap;
int s[N];
bool st[N];//标记是否出队
//如果是false，也就是默认值，说明在队中
int main()
{
	int n=0;//人数
	cin >> n;
	//用1 0分别表示男，女
	for (int i = 1;i <= n;i++)
	{
		//注意让下标从1开始
		char ch;
		cin >> ch;
		if (ch == 'B') s[i] = 1;
		//是女孩不用管因为数组默认值都是0
	}
	//存储技术
	for (int i = 1;i <= n;i++)
	{
		//技术从放到双向链表中
		cin >> e[i];
		ne[i] = i + 1;
		pre[i] = i - 1;
	}
	//手动设置ne[n]
	ne[n] = 0;//0表示没有这个人
	//存放技术差
	for (int i = 2;i <= n;i++)//循环n-1次
	{
		//判断是否为异性
		if (s[i] != s[i - 1])
		{
			//存放技术差绝对值
			heap.push({ abs(e[i] - e[i - 1]),i-1,i });
		}
	}
	vector<node> tmp;//暂存结果
	//这个暂存结果tmp的意义是，咱们得先输出输出的对数
	while (!heap.empty())
	{
		node t = heap.top();
		heap.pop();
		int num = t.num;int i = t.i;int j = t.j;
		if (st[i] || st[j]) continue;
		//如果i,j已经出队的话，则说明i和i-1的技术差和j和j+1的技术差已经无效了
		//所以说如果无效数据了，咱们就跳过该循环

		//循环操作
		tmp.push_back(t);//插入暂存数据
		st[i] = st[j] = true;//设置标记数组

		//调整双向队列
		ne[pre[i]] = ne[j];
		pre[ne[j]] = pre[i];

		//删除这对狗男女（bushi）之后，还要判断接下来爱着的两个人是不是一对
		int left = pre[i];int right = ne[j];
		//重新插入的时候要判断，left和right是否存在
		if (left&&right&&s[left] != s[right])
		{
			heap.push({ abs(e[left] - e[right]),left,right });
		}
	}
	//打印暂存数据
	cout << tmp.size() << endl;
	//这里用一个范围for
	for (auto& e : tmp)
	{
		cout << e.i << " " << e.j << endl;
	}
}

        好了。今天的内容就分享到这，我们下期再见！