建官网个人网站,wordpress 多站点 固定链接,酒厂网站源码,惠州百度推广排名题目链接#xff1a;P1878 舞蹈课 - 洛谷 | 计算机科学教育新生态
1.题目解析 1#xff1a;我们可以发现任意两个相邻的都是异性#xff0c;所以他们的舞蹈技术差值我们都要考虑#xff0c;4和2的差值是2#xff0c;2和4的差值是2#xff0c;4和3的差值是1#xff0c;根…题目链接P1878 舞蹈课 - 洛谷 | 计算机科学教育新生态
1.题目解析 1我们可以发现任意两个相邻的都是异性所以他们的舞蹈技术差值我们都要考虑4和2的差值是22和4的差值是24和3的差值是1根据题目找到1这个最小差值后输出这一对舞伴的编号即下标3和4再输出队列里面还剩的另一队舞伴的编号1和2这里成功出列了两对舞伴所以先输出总对数2再输出3 4再输出1 2 2.算法原理
解法利用小根堆存所有相邻异性的差值然后每次拿出最小的即可 举个例子把全部相邻异性的差值算出来之后拿最小的差值此时最小的差值是2根据题目如果不止一对那么最左边的那一对出列所以让2号3号舞伴出列接着继续让下一个差值最小的舞伴出列这个想法很正确就是利用堆存放相邻异性的差值然后每次拿出最小的就行了但是这个想法会很多问题
1.取出相邻的一对异性之后他们的左右有可能变成新的一对
比如现在让最小差值为2的一对舞伴出列原来在他们左边的男生和右边的女生会组成一对新的舞伴如何能做到快速地删除完一个之后还能把左右两个连接起来呢就可以利用双向链表存队列 比如2和4舞伴出列后让10指向77指向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 cmathusing namespace std;const int N 2e5 10;int n;
int s[N]; //标记男女 - 1/0//双向链表存数据
//数据是从左向右依次进来的4的右边就是22的左边就是4
//直接把它定义出来就行了,就不需要hid这些指针了
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_queuenode 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.提取结果//我们最后要先输出有多少对出列所以要先把结果存起来vectornode 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的编号是11的左边是不存在人的所以也要判断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存结果 //暂存结果vectorpairint, 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;}
