首页 > 其他分享 >洛谷题单指南-二叉堆与树状数组-P1878 舞蹈课

洛谷题单指南-二叉堆与树状数组-P1878 舞蹈课

时间:2024-11-13 09:19:07浏览次数:1  
标签:node 出列 int 洛谷题 二叉 flag right P1878 配对

原题链接: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

相关文章

  • 力扣 653. 两数之和 IV 二叉树/binary-tree two-sum IV
    数组系列力扣数据结构之数组-00-概览力扣.53最大子数组和maximum-subarray力扣.128最长连续序列longest-consecutive-sequence力扣.1两数之和N种解法two-sum力扣.167两数之和IItwo-sum-ii力扣.170两数之和IIItwo-sum-iii力扣.653两数之和IVtwo-sum-IV力......
  • 全局平衡二叉树 (GBST) 小记
    全局平衡二叉树(GBST)小记以下全局平衡二叉树简称\(\text{GBST(GlobelBalancedSearchTree)}\)。我认识的大多数人,对\(\text{GBST}\)的理解基本上都是静态\(\text{LCT}\),或者静态\(\text{TopTree}\),不过我对\(\text{LCT}\)的理解可能还差一点,所以我不打算从阉割\(......
  • 二叉搜索树实现教程:用C++实现数据存储与查找
    文章目录1.二叉搜索树的概念2.二叉搜索树的性能分析3.二叉搜索树的插入4.二叉搜索树的查找5.二叉搜索树的删除6.⼆叉搜索树的实现代码7.⼆叉搜索树key和key/value使⽤场景7.1key搜索场景:7.2key/value搜索场景:7.3key/value⼆叉搜索树代码实现1.二叉搜索树......
  • 计算二叉树(二叉链表)的带权路径长度
    方法1#include<bits/stdc++.h>#defineintlonglong#definemod998244353usingnamespacestd;usingpii=pair<int,int>;typedefstructBtnode{ intdata; structBtnode*lc,*rc; }*Btree,Btnode;//笔试这个可以放上面,但是真的写程序应该把getwpl放在g......
  • 洛谷题单103数组题解||by红糖
    P1428小鱼比可爱题目描述人比人,气死人;鱼比鱼,难死鱼。小鱼最近参加了一个“比可爱”比赛,比的是每只鱼的可爱程度。参赛的鱼被从左到右排成一排,头都朝向左边,然后每只鱼会得到一个整数数值,表示这只鱼的可爱程度,很显然整数越大,表示这只鱼越可爱,而且任意两只鱼的可爱程度可能一样......
  • 101. 对称二叉树
    题目链接解题思路检查一个二叉树是否轴对称,其实和根结点无关,而是和其左右子树有关。左子树头等于右子树头,然后递归调用,「左子树的右儿子」要等于「右子树的左儿子」并且「左子树的左儿子」要等于「右子树的左儿子」。代码/***Definitionforabinarytreenode.......
  • 洛谷题单指南-二叉堆与树状数组-P2085 最小函数值
    原题链接:https://www.luogu.com.cn/problem/P2085题意解读:有n个函数,函数中x取值>=1,计算所有函数能得到的值中最小的m个。解题思路:函数中x取值是>=1的整数,因此每个函数的值是f(1),f(2),f(3)....,是一个递增序列,题目本质上是要从n个递增序列中找到前m个最小的数。首先,对所有函数......
  • 96. 不同的二叉搜索树
    题目链接解题思路暴力怎么做?n个节点,我们要先选头节点i,头节点选中之后,左子树的节点数就决定了,右子树的节点数也就决定了,所以选择头节点i后,不同的数目是左子树不同数目*右子树不同数目,这又是子问题了,又可以递归得到结果。有一个细节,假设n等于5,1,2,3,4,5,假设现在选择了3为头......
  • leetcode1008. 前序遍历构造二叉搜索树
    给定一个整数数组,它表示BST(即 二叉搜索树 )的 先序遍历 ,构造树并返回其根。保证 对于给定的测试用例,总是有可能找到具有给定需求的二叉搜索树。二叉搜索树 是一棵二叉树,其中每个节点, Node.left 的任何后代的值 严格小于 Node.val , Node.right 的任何后代的值......
  • 代码随想录——二叉树-12.平衡二叉树
    自顶向下递归(前序遍历)这种方法是一开始想到的,虽然ac了但是对于它的本质却不清不楚,不知道时间复杂度,不知道属于前序遍历。思路首先得到root节点的左右子树的深度(左右),若深度差绝对值大于1(中),则root为根的树不是平衡二叉树;否则继续递归root的左右子树,其左右子树都是平衡二叉树......