原题链接:https://www.luogu.com.cn/problem/P1878
题意解读:n个男女排列一行,每人舞蹈技术是ai,每次找到相邻男女舞蹈技术差值绝对值最小的一对出列,输出每对出列的人员编号。
解题思路:
设初始有8人编号为:1 2 3 4 5 6 7 8
将1 2, 2 3, 3 4, 4 5, 5 6, 6 7, 7 8中是男女的配对编号以及ai的差值存入小根堆
循环处理小根堆堆顶
假设第一次出列的配对是4 5
那么与4和5相关的其他配对就没有存在的必要,如3 4,5 6这些配对在处理时可以舍去
另外,由于4 5出列,队伍变成1 2 3 6 7 8
3 6会成为新的可能的配对,需要动态加入小根堆
两个关键问题:
1、当一组配对出列后,与配对相关的其他配合如何舍去
可以借助标记数组flag[N],记录每个编号是否出列,当取优先队列堆顶时,判断该组配对里的人员是否已经出列,如果出列则舍去
2、当一组配对出列后,该配对两侧的人会产生新的配对
可以通过ll[N],rr[N]两个数组,动态维护每个编号左边是谁、右边是谁,这样当有配对出列,只需要取配对左边人员的左边,配对右边人员的右边,组成新的配对即可
100分代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n;
char s[N];
int a[N];
bool flag[N]; //标记已出列的编号
int ll[N], rr[N]; //每个人左边、右边是谁
struct Node
{
int l, r;
bool operator < (const Node &node) const &
{
if(abs(a[l] - a[r]) != abs(a[node.l] - a[node.r]))
return abs(a[l] - a[r]) > abs(a[node.l] - a[node.r]); //差值绝对值小的在堆顶
return l > node.l; //差值一样,更左边的在堆顶
}
};
priority_queue<Node> q; //保存潜在的配对
int ansl[N], ansr[N], cnt;
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> s[i];
for(int i = 1; i <= n; i++)
{
cin >> a[i];
ll[i] = i - 1;
rr[i] = i + 1;
if(i > 1)
{
if(s[i] != s[i - 1])
{
q.push({i - 1, i});
}
}
}
while(q.size())
{
if(flag[q.top().l] || flag[q.top().r]) //如果配对中的某个已经出列,该配对也不存在
{
q.pop();
continue;
}
Node node = q.top(); q.pop();
cnt++;
ansl[cnt] = node.l;
ansr[cnt] = node.r;
flag[node.l] = flag[node.r] = true; //标记已出列
int node_left = ll[node.l]; //已出列配对左边的左边
int node_right = rr[node.r]; //已出列配对右边的右边
if(node_left < 1 || node_right > n) continue;
rr[node_left] = node_right;
ll[node_right] = node_left;
if(s[node_left] != s[node_right]) q.push({node_left, node_right});
}
cout << cnt << endl;
for(int i = 1; i <= cnt; i++) cout << ansl[i] << " " << ansr[i] << endl;
return 0;
}
标签:node,出列,int,洛谷题,二叉,flag,right,P1878,配对 From: https://www.cnblogs.com/jcwy/p/18541992