题目
题目描述:有一个长度为N的序列。一开始,这个序列是1, 2, 3,... n - 1, n的一个排列。
对这个序列,可以进行如下的操作:
每次选择序列中k个连续的数字,然后用这k个数字中最小的数字替换这k个数字中的每个数字。
我们希望进行了若干次操作后,序列中的每个数字都相等。请你找出需要操作的最少次数。
输入描述:
第一行:两个数字n, k,含义如题,满足2 <= k <= n <= 105;
第二行:n个数字,是1, 2, 3,...n的一个排列。
一个整数,表示最少的次数。
解析
首先这道题,我们经过我们不缜密的分析发现:这就是一道思考题呀。
首先我们看看题目:
- 题目告诉这是一组从1开始的数字排列;而且我们要取出k个数变成里面的最小数,最后将所有数字化为同一个数。
- 所以我们不用缜密就得到了:最后这n个数的结果都一定是1(最小的那个)。
然后简单讲一下我一开始的思路(有误思路):
- 我们可以先标记好我们这个1(最小值点),然后以1为中心发散。这样像两边扩散就不会有变成其他数字的次数浪费。
- 我简简单单举了两个例子之后,发现似乎1在区段中间或边上好像没区别(最大错误)。所以向左和右边进行发散,得到了以下代码:
ans = ceil(1.0 * (n - 1 - k) / (k - 1)) + ceil(1.0 * k / (k - 1));
- 首先往左边和往右边都一定是在包括1的情况下,选择一个k大小的区域进行操作。(在这里我们就让1成为了左右顶点)
- 为什么是k - 1呢?因为k大小的区域里面一定有一个在前面(或后面)的区域中。所以判断操作次数就是:区块长度/(k - 1)。
- 但是这里错了,甚至只能过20%。
那什么为什么错了呢?
- 错的主要原因我也说了:就是我们认为1的位置不影响答案。实则当k在中间的时候可能减少两边的浪费(减小浮点误差)。
那怎么改呢?
- 也很简单。既然我们知道了错误的根源:我们要做的就是让1在区间中间的情况也成立。有两种方法。
第一种方法:遍历1在区间内每个位置的情况!
- 我们知道k某位置取值有误差,所有我们只要全算一遍就好了。
- 怎么算:我们只要求出k区间以外的左边和右边有几个扩张区间就可以了(和前面方法类似,但是最后记得加上自己这个区间的一次操作)。
第二种方法:不管1的位置直接来!
- 其实在算两端分值的时候,我就想过,这两边能不能合起来?但是因为两边要去ceil(向上取整),我就放弃了。
- 但是后来我发现,其实合起来并不是说,会造成误差,而是减小了误差。
- 减小误差怎么说呢?我们现在要求最小的区间个数:就按我们平时取平均的思想,是不是整个区间除一下,向上取整就是最小区间数了?
- 所以呢我们可以两边直接来!但是这个时候你会说了,直接来怎么行呢?1咋办。——>莫得关系,我们来看下面。
- 按照上面的方法,我们求扩展空间就可以得到这么一个公式:
int ans = ceil(1.0 * (n - 1) / (k - 1));
首先是n - 1,这是因为我们去掉了1的位置。其次是k - 1,和上面的理由一样,k的区域有一个数是被包含的。 - 这个时候我们再把1拿出来看,1有两种情况:被一个区间包含;或者在两个区间中间。但是,1终究可以和一个区域组成一个区间!
- 所以除了这个区间以外:其他所有的空间都是1的拓展空间!
- 484很很很很很简单哈哈哈哈~~~~~
代码敲起来:
- 数组储存数组。
- 特判1,做标记。
- 按上面教的算个公式。
- 看代码趴~
AC代码
#include <iostream> #include <cmath> using namespace std; #define IOS ios::sync_with_stdio(false); //代码预处理区 const int MAX = 1e5 + 7; int f[MAX]; //全局变量区 int main() { IOS; int n, k; cin >> n >> k; int pos = 0; for (int i = 0; i < n; i++) { cin >> f[i]; if (1 == f[i]) pos = i; } int ans = ceil(1.0 * (n - 1) / (k - 1)); cout << ans << endl; return 0; } //函数区