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;}