牛客算法周周练5 C 序列最小化

题目大意

给定 1 ~ n 的一个排列, 每次选择序列中 k 个连续的数字，全部替换为其中最小的数. 询问最少的次数.

分析

应该不难想到, 最终, 序列中的每一个数都将变为 1. 那么就从 1 的位置开始, 连续选 k 个数, 变为 1 即可.
不过, 操作完后, 会发现, 其实从序列一端开始选即可, 每次和上次 k 个数中最后一个数开始即可.

代码

#include <cstdio>
#include <cstring>

using namespace std;

const int SIZE = 1e5 + 5;

int arr[SIZE];
int main()
{
    int n, k;
    int ans;

    scanf("%d %d", &n, &k);
    for (register int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);

    ans = 0;
    if (n <= k)
        ans = 1;
    else
    {
        n -= k;
        ans++;
        k--;
        ans += n / k;
        if (n % k != 0)
            ans++;
    }
    printf("%d\n", ans);

    return 0;
}