牛客练习赛47 C DongDong跳一跳(线段树+思维)
发布日期:2021-05-08 15:15:36 浏览次数:25 分类:精选文章

本文共 1909 字,大约阅读时间需要 6 分钟。

问题分析与解决思路

在本题中,我们需要找到一个位置,使得在该位置停下时所能获得的鱼竿量最大。具体来说,对于每一个位置i,我们需要确定他停在该位置时所能覆盖的区间[a[i]-m, a[i]+m],并在此区间内找到最大值。为了高效地解决这个问题,我们可以使用线段树来维护区间内的最大值。

技术细节解释

构建线段树

  • 线段树定义

    • 线段树是一个基于二叉树的数据结构,能够在O(log n)的时间复杂度内完成多个查询操作。
    • 每个节点存储其对应区间内的最大值。
  • 初始化线段树

    • 线段树的每个叶子节点对应一个位置,存储该位置的鱼竿量。
    • 非叶子节点的值是其左右子节点中的最大值。
  • 构建过程

    • 递归地将区间分割成两部分,直到区间长度为1时,叶子节点的值被确定。
    • 非叶子节点的值通过比较左右子节点的值来确定。
  • 查询操作

  • 查询函数

    • 该函数负责查询某个区间[l, r]内的最大值。
    • 通过递归地比较当前节点的区间是否与查询区间相交,进而决定需要查询哪些子节点。
  • 查询过程

    • 如果当前节点的区间完全在查询区间内,则直接返回节点的最大值。
    • 否则,递归查询左边和右边子节点,并取最大值。
  • 更新操作

  • 更新函数

    • 该函数用于更新某个位置的鱼竿量值。
    • 根据位置的值,递归地更新对应的线段树节点。
  • 更新过程

    • 如果当前节点的区间长度为1,则直接更新该节点的值。
    • 否则,判断目标位置是否在左边或右边子节点中,并递归更新相应的子节点。
  • 代码实现

    #include 
    using namespace std;const int maxn = 1e6 + 1000;typedef long long ll;struct cxk { int l, r; ll w;};tree[maxn << 1] cxk;int n, m, a[maxn], b[maxn];void build(int l, int r, int x) { cxk[x].l = l; cxk[x].r = r; if (l == r) { cxk[x].w = 0; return; } int mid = (l + r) >> 1; build(l, mid, x << 1); build(mid + 1, r, x << 1 | 1); cxk[x].w = max(cxk[x << 1].w, cxk[x << 1 | 1].w);}void update(int pos, ll v, int x) { if (cxk[x].l == cxk[x].r) { cxk[x].w = v; return; } int mid = (cxk[x].l + cxk[x].r) >> 1; if (pos <= mid) { update(pos, v, x << 1); } else { update(pos, v, x << 1 | 1); } cxk[x].w = max(cxk[x << 1].w, cxk[x << 1 | 1].w);}ll query(int l, int r, int x) { if (l > cxk[x].r || cxk[x].l > r) { return 0; } if (l <= cxk[x].l && cxk[x].r <= r) { return cxk[x].w; } int mid = (cxk[x].l + cxk[x].r) >> 1; ll ans = 0; if (l <= mid) { ans = max(ans, query(l, r, x << 1)); } if (mid + 1 <= r) { ans = max(ans, query(l, r, x << 1 | 1)); } return ans;}

    代码解释

    • 线段树结构cxk结构用于存储线段树节点的区间信息和最大值。
    • 构建函数build函数负责初始化线段树,递归地将区间分割并更新最大值。
    • 更新函数update函数用于更新某个位置的值,递归地更新线段树。
    • 查询函数query函数用于查询区间内的最大值,递归地比较子节点区间并返回最大值。

    通过上述方法,我们可以高效地找到每个位置停下的最大鱼竿量,从而解决问题。

    上一篇:Codeforces Round #553 (Div. 2) B. Dima and a Bad XOR(异或+思维)
    下一篇:Codeforces Round #620 (Div. 2) C. Air Conditioner(思维)

    发表评论

    最新留言

    第一次来,支持一个
    [***.219.124.196]2025年05月10日 14时50分23秒