题解 | 序列最小化 (两行代码)

题目描述

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

目标是把所有的数都替换成1
贪心地想，每次选取包含一个1的长度为k的连续序列，都可以把其他的k - 1个数替换成。总共需要把其他n - 1个数全部替换成1，所以答案为

至于初始状态1的位置是否有影响，我们可以考虑用从左往右用长度为k的线段覆盖整个序列，相邻的两个线段相交的长度为1。我们发现，依次选择这些线段，每次选择包含1的，即可达成目的。

#include<cstdio>
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    printf("%d", (n - 1) / (m - 1) + ((n - 1) % (m - 1) ? 1 : 0));
    return 0;
}