跳跳乐

• 跳跳乐
  • 题目
    • 描述
    • IO格式
    • 样例
  • 解答
    • 思路
    • 代码
    • 时空消耗

题目

by 陈宇豪

描述

有 M 个间距为 1 的台阶; 有一只青蛙, 可以从一个台阶前往间距不大于 K、高度差不大于 H 的另一个台阶, 求可以互相跳跃的台阶对数.

IO格式

输入:

M K H
台阶高度...

输出:

可以互相跳跃的台阶对数

样例

输入:

9 5 2
6 8 5 7 4 3 9 2 10

输出:

14

解答

思路

本题对速度要求很高, 主要需要借助两个重要方法——快排和二分查找. 通过 #include <algorithm>, 可以得到比快排更快的快排 std::sort, 和拟序二分法 std::lower_bound 与偏序二分法 std::upper_bound. 拟序二分法用于求下界, 偏序二分法用于求上界.

首先, 创建一个队列, 每输入一个高度就入队, 以此来判断台阶的顺序. 接着, 我们用于处理的台阶数组为 ui steps[K + 1], 在 steps 之内的台阶总是满足间距条件.

• 先对前 K + 1 个进行处理, 得到它们之间能互相跳跃的对数; 这一步可以通过对 steps[1 : K] 向其左侧做高度条件下界二分来得到.

• 然后, 每新输入一个台阶 ui cur, 就从队列中取出已经被完全遍历的元素 ui first. 先二分找到 cur 应当被放置的位置, 然后根据 cur 与 first 的大小关系判断方向并冒泡插入 cur、去除 first.

• 之后, 对 cur 求高度条件上下界二分, 计算总和即得结果.

代码

#include <algorithm>
#include <cstdio>
#include <queue>
using namespace std;

#define prf printf
#define scf scanf
using ui = unsigned int;
using ull = unsigned long long;

ui M;
ui K, H;
ui* steps;
queue<ui> stepsIn;
ull sum = 0;

// 预处理前K + 1个
inline void Pre(ui len) {
    for (ui i = 0; i < len; i++) {
        scf("%u", &steps[i]);
        stepsIn.push(steps[i]);
    }
    sort(steps, steps + len);
    for (ui i = 1; i < len; i++) {
        auto hLim = steps[i] > H ? steps[i] - H : 0;
        sum += &steps[i] - lower_bound(steps, steps + i + 1, hLim);
    }
}

// 返回cur排序后位置
inline ui* Insert(ui cur) {
    auto first = stepsIn.front();
    stepsIn.pop();
    auto* pfirst = lower_bound(steps, steps + K + 1, first);
    if (cur < first) {
        auto* pcur = lower_bound(steps, pfirst, cur);
        auto istart = pfirst - steps;
        auto istop = pcur - steps;
        for (ui i = istart; i > istop; i--) steps[i] = steps[i - 1];
        *pcur = cur;
        return pcur;
    } else {
        auto* pcur = upper_bound(pfirst + 1, steps + K + 1, cur) - 1;
        auto istart = pfirst - steps;
        auto istop = pcur - steps;
        for (ui i = istart; i < istop; i++) steps[i] = steps[i + 1];
        *pcur = cur;
        return pcur;
    }
}

int main() {
    scf("%u%u%u", &M, &K, &H);
    steps = new ui[K + 1];
    if (K + 1 >= M)
        Pre(M);
    else {
        Pre(K + 1);
        for (ui i = K + 1; i < M; i++) {
            ui cur;
            scf("%u", &cur);
            auto* pcur = Insert(cur);
            auto hLim1 = cur > H ? cur - H : 0;
            auto hLim2 = cur + H;
            auto* phLim1 = lower_bound(steps, pcur + 1, hLim1);
            auto* phLim2 = upper_bound(pcur, steps + K + 1, hLim2) - 1;
            sum += (pcur - phLim1) + (phLim2 - pcur);
        }
    }
    prf("%llu", sum);
    delete[] steps;
    return 0;
}

时空消耗

1	Accepted	0 ms	936 KB
2	Accepted	32 ms	1000 KB
3	Accepted	108 ms	1080 KB
4	Accepted	160 ms	1168 KB
5	Accepted	0 ms	936 KB
6	Accepted	412 ms	1088 KB
7	Accepted	508 ms	1320 KB
8	Accepted	568 ms	1320 KB
9	Accepted	632 ms	1320 KB
10	Accepted	628 ms	1316 KB