题解 P1878 【舞蹈课】

作为一个标签党，点开标签发现是**二叉堆** 众所周知，嗯，没错，就是二叉堆 ## 算法流程 ``` 1.先定义一个结构体堆 + 重载运算符 2.把男女的性别在f数组里表示好 3.把相邻的舞者入队（不能同性别） 4.找到符合条件（舞蹈技术相差最小的那一对会出列并开始跳舞。如果不止一对， 那么最左边的那一对出列）的舞者出队，并定义为“跳过了” 5.再找一对从上一对跳舞的人继续找相邻的舞者入队（得一男一女） 6.输出 + AC ``` 先讲一下代码里有的一些~~并不是很难的~~东西吧~ ## 1.priority_queue 称为**堆**，也叫**优先队列**，是一种**二叉树** 至于**小根堆**和**大根堆**么~（~~就不说了，搜百度去吧~~）简单的提一下吧（~~怕被差评~~） ``` 大根堆：堆顶元素最大，像一颗二叉树一样，越往下越小 小根堆：堆顶元素最小，像一颗二叉树一样，越往下越大 ``` 堆的那些~~简单~~操作就上网百度去吧 **定义个堆默认是大根堆**，所以重载运算符（定义结构体的排序方式）的时候要注意（最重要，~~敲黑板~~）把**运算符反过来** ## 2.pair 是一种~~常用的~~**数据结构** 简单的提一下吧 ``` pair顾名思义，是一对的意思，在数据结构中也如此 ``` **定义：** ```cpp pair < 第一个的变量类型, 第二个的变量类型 > 变量或数组名称 ``` 先用做int int ans[10001]吧 **第一个元素：** ```cpp ans[i].first ``` **第二个元素：** ```cpp ans[i].second ``` 先讲这么多吧（~~额，这才几个字~~），够了 好了，看代码（~~终于到代码了，累死了~~） code ： ```cpp //代码里的register均可省去，是用于优化的 #include <bits/stdc++.h> using namespace std; pair < int, int > ans[1000001];//定义pair来存答案 int n, q[1000001], z;//z是答案总数 string s; bool vis[1000001], f[1000001];//vis是用来判断是否选过这个人，f数组表示是男是女(男是true，女是false) /* struct node { int x, y, z; friend bool operator < (node a, node b) { if(a.z == b.z) { return a.x < b.x; } else { return a.z < b.z; } } }; */ struct node { int x, y, z;//x为其中一个舞者的编号，y为另一个，z为舞技之差 friend bool operator < (node a, node b) { if(a.z == b.z) { return a.x > b.x;//priority_queue默认大根堆，要反过来写 } else { return a.z > b.z;//同理 } } };//不用定义结构体数组 priority_queue < node, vector < node > > pru;//加不加vector都一样，加能更快一些 int main() { scanf("%d", &n); cin >> s; for(register int i = 0; i < n; ++i) { if(s[i] == 'B')//用f数组表示男女 { f[i + 1] = true;//要加一(string是从0 ~ n - 1的) } else//不是男就是女 { f[i + 1] = false; } } for(register int i = 1; i <= n; ++i) { scanf("%d", &q[i]); } for(register int i = 1; i < n; ++i) { if(f[i] != f[i + 1])//不能男和男跳舞，女和女跳舞 { pru.push((node){i, i + 1, abs(q[i] - q[i + 1])/*要加abs*/});//可以把它们强制转化到一个结构体里 } } while(!pru.empty()) { int x = pru.top().x;//取出第一个人来 int y = pru.top().y;//取出第二个人来 pru.pop();//pop掉 if(!vis[x] && !vis[y])//不能有一个人跳过舞了 { vis[x] = true;//改成跳过了 vis[y] = true; ans[++z].first = x;//存答案 ans[z].second = y;//z只加一遍 //再找一对儿相邻的入队 //x向左边，y向右边(因为x小，y大) while(x > 0 && vis[x])//跳过了或小于零都不行 { --x;//往左边 } while(y <= n && vis[y])//跳过了或大于n都不行 { ++y;//往右边 } if(x > 0 && y <= n/*有点多余*/ && f[x] != f[y])//不能男和男或女和女啊 { pru.push((node){x, y, abs(q[x] - q[y])});//强制转化成结构体再入队 } } } printf("%d\n", z);//先输出总数 for(register int i = 1; i <= z; ++i) { printf("%d %d\n", ans[i].first, ans[i].second);//输出舞者 } return 0; } ``` ### 求过 + 求赞