洛谷题单指南-分治与倍增-P3509 [POI2010] ZAB-Frog

原题链接：https://www.luogu.com.cn/problem/P3509

题意解读：n个点，每个点上有一只青蛙每次跳到距离自己第k近的点，m次之后跳到哪个点。

解题思路：

1、计算距离每个点第k近的点，存入ne[N]

给定一个点i，距离i第k近的点一定在长度为k+1个点的窗口内，窗口包括i

并且，第k近的点只能是左端点或者右端点，取距离i较远者

当右端点下一个点距离i比i到左端点距离还小，窗口需要右移一位

因此，整个过程可以用双指针来实现

int l = 1, r = k + 1;
for(int i = 1; i <= n; i++)
{
    while(r + 1 <= n && a[r + 1] - a[i] < a[i] - a[l]) l++, r++;
    if(a[r] - a[i] > a[i] - a[l]) ne[i] = r;
    else ne[i] = l;
}

2、计算每个点跳m次之后到达的点

如果直接枚举，必然会超时，可以借助倍增思想，通过快速幂的模型来调m次

while(m)
{
    if(m & 1) 更新每个点跳到ne[i];
    m = m >> 1;
    更新ne[i]到ne[ne[i]];
}

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1000005;

long long n, k, m;
long long a[N];
int ne[N]; //ne[i]表示第i个位置的下一个位置，也就是距离i第k近的点
int ne2[N]; //防止ne数组被覆盖而定义一个滚动数组
int ans[N];

int main()
{
    cin >> n >> k >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];

    //计算ne[]，双指针控制窗口滑动，距离a[i]第k近的点一定在连续k+1个点的两端，取距离a[i]较远的那一个
    //但如果右端点的下一个位置距离a[i]小于a[i]到左端点距离， 窗口向右滑动
    int l = 1, r = k + 1;
    for(int i = 1; i <= n; i++)
    {
        while(r + 1 <= n && a[r + 1] - a[i] < a[i] - a[l]) l++, r++;
        if(a[r] - a[i] > a[i] - a[l]) ne[i] = r;
        else ne[i] = l;
    }

    //初始位置
    for(int i = 1; i <= n; i++) ans[i] = i;

    //倍增跳m次，快速幂模型
    while(m)
    {
        if(m & 1) 
        {
            for(int i = 1; i <= n; i++) ans[i] = ne[ans[i]];
        }
        m = m >> 1;
        memcpy(ne2, ne, sizeof(ne)); //复制ne到ne2
        for(int i = 1; i <= n; i++) ne[i] = ne2[ne[i]];// //ne2是在ne基础上连续跳两次,循环中ne会被覆盖，ne2起到滚动数组的作用
    }

    for(int i = 1; i <= n; i++) cout << ans[i] << " ";

    return 0;
}