题目

题目描述:
有一个长度为N的序列。一开始,这个序列是1, 2, 3,... n - 1, n的一个排列。
对这个序列,可以进行如下的操作:
每次选择序列中k个连续的数字,然后用这k个数字中最小的数字替换这k个数字中的每个数字。
我们希望进行了若干次操作后,序列中的每个数字都相等。请你找出需要操作的最少次数。

输入描述:
第一行:两个数字n, k,含义如题,满足2 <= k <= n <= 105;
第二行:n个数字,是1, 2, 3,...n的一个排列。

输出描述:
一个整数,表示最少的次数。


解析

首先这道题,我们经过我们不缜密的分析发现:这就是一道思考题呀。

首先我们看看题目:
  1. 题目告诉这是一组从1开始的数字排列;而且我们要取出k个数变成里面的最小数,最后将所有数字化为同一个数。
  2. 所以我们不用缜密就得到了:最后这n个数的结果都一定是1(最小的那个)

然后简单讲一下我一开始的思路(有误思路)
  1. 我们可以先标记好我们这个1(最小值点),然后以1为中心发散。这样像两边扩散就不会有变成其他数字的次数浪费。
  2. 我简简单单举了两个例子之后,发现似乎1在区段中间或边上好像没区别(最大错误)。所以向左和右边进行发散,得到了以下代码:
    ans = ceil(1.0 * (n - 1 - k) / (k - 1)) + ceil(1.0 * k / (k - 1));
  3. 首先往左边和往右边都一定是在包括1的情况下,选择一个k大小的区域进行操作。(在这里我们就让1成为了左右顶点)
  4. 为什么是k - 1呢?因为k大小的区域里面一定有一个在前面(或后面)的区域中。所以判断操作次数就是:区块长度/(k - 1)。
  5. 但是这里错了,甚至只能过20%。

那什么为什么错了呢?
  1. 错的主要原因我也说了:就是我们认为1的位置不影响答案。实则当k在中间的时候可能减少两边的浪费(减小浮点误差)。

怎么改呢?
  • 也很简单。既然我们知道了错误的根源:我们要做的就是1在区间中间的情况也成立。有两种方法。

第一种方法:遍历1在区间内每个位置的情况!
  1. 我们知道k某位置取值有误差,所有我们只要全算一遍就好了。
  2. 怎么算:我们只要求出k区间以外的左边和右边有几个扩张区间就可以了(和前面方法类似,但是最后记得加上自己这个区间的一次操作)。

第二种方法:不管1的位置直接来!
  1. 其实在算两端分值的时候,我就想过,这两边能不能合起来?但是因为两边要去ceil(向上取整),我就放弃了。
  2. 但是后来我发现,其实合起来并不是说,会造成误差,而是减小了误差
  3. 减小误差怎么说呢?我们现在要求最小的区间个数:就按我们平时取平均的思想,是不是整个区间除一下,向上取整就是最小区间数了?
  4. 所以呢我们可以两边直接来!但是这个时候你会说了,直接来怎么行呢?1咋办。——>莫得关系,我们来看下面。
  5. 按照上面的方法,我们求扩展空间就可以得到这么一个公式:
    int ans = ceil(1.0 * (n - 1) / (k - 1));
    
    首先是n - 1,这是因为我们去掉了1的位置。其次是k - 1,和上面的理由一样,k的区域有一个数是被包含的。
  6. 这个时候我们再把1拿出来看,1有两种情况:被一个区间包含;或者在两个区间中间。但是,1终究可以和一个区域组成一个区间!
  7. 所以除了这个区间以外:其他所有的空间都是1的拓展空间!
  8. 484很很很很很简单哈哈哈哈~~~~~

代码敲起来:
  1. 数组储存数组。
  2. 特判1,做标记。
  3. 按上面教的算个公式。
  4. 看代码趴~


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;
}
//函数区