洛谷P3509 Frog

题目

首先分析数据范围发现m很大，所以线性做法肯定不行，因此考虑倍增，即预处理出每个点跳1次后的位置。然后只用两个数组类似于快速幂，推出每个点跳m次后的位置。

预处理离每个点第k小的点，可以用长度为k的尺子尺取。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

#define int long long

#define N 1001011

using namespace std;

int n, k, m;

int data[N], jum[N], ans[N], temp[N];

inline void init()

{

	scanf("%lld%lld%lld", &n, &k, &m);

	for (int i = 1; i <= n; i++)

		scanf("%lld", &data[i]), ans[i] = i;

	jum[1] = k + 1;

	int l = 1, r = k + 1;

	for (int i = 2; i <= n; i++)

	{

		while (r + 1 <= n && (data[r + 1] - data[i]) < (data[i] - data[l]) ) l++, r++;

		if (data[r] - data[i] > data[i] - data[l])

			jum[i] = r;

		else

			jum[i] = l;

	}

}

signed main()

{

	init();

	while (m)

	{

		if (m & 1)

			for (int i = 1; i <= n; i++)

				ans[i] = jum[ans[i]];

		m >>= 1;

		for (int i = 1; i <= n; i++)

			temp[i] = jum[i];

		for (int i = 1; i <= n; i++)

			jum[i] = temp[temp[i]];

	}

	for (int i = 1; i <= n; i++)

		printf("%d ", ans[i]);

	return 0;

}

巴特西

洛谷P3509 Frog

最新文章

热门文章