P1878 舞蹈课（详解）c++

题目链接：P1878 舞蹈课 - 洛谷 | 计算机科学教育新生态

1.题目解析

1：我们可以发现任意两个相邻的都是异性，所以他们的舞蹈技术差值我们都要考虑，4和2的差值是2，2和4的差值是2，4和3的差值是1，根据题目找到1这个最小差值后，输出这一对舞伴的编号即下标3和4，再输出队列里面还剩的另一队舞伴的编号1和2，这里成功出列了两对舞伴，所以先输出总对数2再输出3 4再输出1 2

2.算法原理

解法：利用小根堆存所有相邻异性的差值，然后每次拿出最小的即可

举个例子，把全部相邻异性的差值算出来之后，拿最小的差值，此时最小的差值是2，根据题目如果不止一对，那么最左边的那一对出列，所以让2号3号舞伴出列，接着继续让下一个差值最小的舞伴出列，这个想法很正确，就是利用堆存放相邻异性的差值，然后每次拿出最小的就行了，但是这个想法会很多问题                  

1.取出相邻的一对异性之后，他们的左右，有可能变成新的一对

比如现在让最小差值为2的一对舞伴出列，原来在他们左边的男生和右边的女生会组成一对新的舞伴，如何能做到快速地删除完一个之后，还能把左右两个连接起来呢，就可以利用双向链表存队列

比如2和4舞伴出列后，让10指向7，7指向10就可以得到一个新队列，利用双向链表存队列，就可以实现删除一对舞伴后，只需修改指针，就可以快速地确定另一个，并且把新的队列还原出来

2.堆中，有可能存在已经出列的人
堆中存放这5个差值8 2 3 2 8，最小差值为2的一对舞伴出列后，1号和4号舞伴产生新的差值3，并把它放到堆里，2号，3号舞伴出列后，8和3就变成了无效元素，但它们还在堆里，此时我拿出3，再输出下标，就有可能出错，所以要杜绝这种情况，创建一个bool数组标记一下即可；true表示出列，false表示没出列，假如我把3拿出来，再判断他对应的舞伴3和4是否有出列的情况，如果有就不对这个3进行处理

3.堆中存什么？
我们要知道技术差以及左边的人是谁以及右边的人是谁，<技术差，左编号，右编号>，这样就能还原双向链表，把技术差拿到，知道左编号和右编号，通过修改指针就可以还原

代码

//舞蹈课
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

const int N = 2e5 + 10;

int n;
int s[N]; //标记男女 - 1/0

//双向链表存数据
//数据是从左向右依次进来的，4的右边就是2，2的左边就是4，
//直接把它定义出来就行了,就不需要h，id这些指针了
int e[N];
int pre[N], ne[N];

struct node {
	int d; //技术差
	int l, r; //左右编号

	//小根堆，大元素下坠 
	bool operator <(const node& x) const
	{
		//根据题目如果不止一对，那么最左边的那一对出列
		//可以知道技术差有可能相等，所以技术差相等的时候可以根据左编号定义小根堆
		if (d != x.d) return d > x.d;
		else return l > x.l;
	}
};

priority_queue<node> heap;
bool st[N]; //标记已经出列的人

int main()
{
	cin >> n; 
	for (int i = 1; i <= n; ++i)
	{
		char ch; cin >> ch;
		if (ch == 'B') s[i] = 1;
	}

	for (int i = 1; i <= n; ++i)
	{
		cin >> e[i];
		//直接创建双向链表
		pre[i] = i - 1;
		ne[i] = i + 1;
	}
	ne[n] = 0; //0表示后面没有元素

	//1.先把所有的异性放进堆里
	for (int i = 2; i <= n; ++i)
	{
		//如果当前性别和前一个人的性别不一样
		if (s[i] != s[i - 1])
		{
			heap.push({ abs(e[i] - e[i - 1]), i - 1, i });
		}
	}

	//2.提取结果
	//我们最后要先输出有多少对出列，所以要先把结果存起来
	vector<node> ret; //暂存结果

	//堆里还要异性就一直出列
	while (heap.size())
	{
		node t = heap.top(); heap.pop();
		int d = t.d, l = t.l, r = t.r;
		//l、r其中任何一个标记ture，说明对应的位置里有人已经出列了
		if (st[l] || st[r]) continue;

		ret.push_back(t);
		st[l] = st[r] = true; //标记l或r已经出列

		//维护双向链表
		ne[pre[l]] = ne[r];
		pre[ne[r]] = pre[l];
		
		//判断新的左右是否会成为一对，左和右有可能不存在，判断异性就无意义
		//如果l的编号是1，1的左边是不存在人的，所以也要判断l/r是否存在
		int left = pre[l], right = ne[r];
		if (left && right && s[left] != s[right])
		{
			heap.push({ abs(e[left] - e[right]), left, right });
		}
	}

	cout << ret.size() << endl;	
	for (auto& x : ret)
	{
		cout << x.l << " " << x.r << endl;
	}

	return 0;
}

也可以用pair存结果

	//暂存结果
	vector<pair<int, int>> ret;

	//模拟出列过程
	while (heap.size())
	{
		node t = heap.top(); heap.pop();
		int d = t.d, l = t.l, r = t.r;

		if (st[l] || st[r]) continue; //对应舞伴已出列则不处理

		//记录结果
		ret.push_back({ l,r }); 
		st[l] = st[r] = true; //标记已出列

		//更新双向链表
		int left = pre[l], right = ne[r];
		ne[left] = right;
		pre[right] = left;

		//检查新的相邻是否为异性组合
		//l和r如果是1或者n，那便没有左边人或右边人
		if (left && right && s[left] != s[right])
		{
			heap.push({ abs(e[left] - e[right]), left , right });
		}
	}

	cout << ret.size() << endl;
	for (auto& x : ret)
	{
		cout << x.first << " " << x.second << endl;
	}