【牛客算法周周练5】C-序列最小化
序列最小化
https://ac.nowcoder.com/acm/contest/5556/C
题目
题目描述：有一个长度为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;
}
//函数区比赛 文章被收录于专栏
憨憨的专栏
