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

序列最小化

https://ac.nowcoder.com/acm/problem/17233

题目描述

有一个长度为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;
}
全部评论

相关推荐

07-18 18:09
门头沟学院 Java
点赞 评论 收藏
分享
06-20 17:42
东华大学 Java
凉风落木楚山秋:要是在2015,你这简历还可以月入十万,可惜现在是2025,已经跟不上版本了
我的简历长这样
点赞 评论 收藏
分享
05-29 20:34
门头沟学院 C++
KarlAllen:得做好直接春招的准备。学历差的话,一是面试要求会比学历好的严格不少,二是就算面试通过了也会被排序。总之暑期和秋招对于学历差的就是及其不友好
无实习如何秋招上岸
点赞 评论 收藏
分享
评论
3
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务