题目描述 有一个长度为N的序列。一开始，这个序列是1, 2, 3,... n - 1, n的一个排列。对这个序列，可以进行如下的操作：每次选择序列中k个连续的数字，然后用这k个数字中最小的数字替换这k个数字中的每个数字。我们希望进行了若干次操作后，序列中的每个数字都相等。请你找出需要操作的最少次数。
展开全文
C 序列最小化 题目地址： https://ac.nowcoder.com/acm/contest/5556/C 基本思路： 我们知道这个序列是N个数的全排列，那么很明显要一直替换最小替换到所有数相等，就是所有数都换成1。所以我们肯定第一步要找到包含1的区间替换，然后再从这个区间左右两边，连
展开全文
题意 给一串1..N的序列，顺序任意，然后从中取出连续k个数字，把他们替换成其中最小的数字。 解析 不难看出，最终所有数字都会变成1。 那么首先我们就会想到先去替换包含1的连续k区间，剩下的就左右跑就行了。但最优的情况一定发生在重叠的长度最少的时候。 不妨假设都只重叠1个数字(最优解的情况)，那么此
展开全文
题目描述有一个长度为N的序列。一开始，这个序列是1, 2, 3,... n - 1, n的一个排列。 对这个序列，可以进行如下的操作： 每次选择序列中k个连续的数字，然后用这k个数字中最小的数字替换这k个数字中的每个数字。 我们希望进行了若干次操作后，序列中的每个数字都相等。请你找出需要操作的最少次
展开全文
依据题意可知，在这样一个全排列中，最终所有的数字都会变成1.题目要求我们找的是在满足题意条件下执行最少的次数，而没有问我们如何执行所以我们不妨假设我们每次执行的都是最优的，这应当有在大于k-1个数字不为1的条件下，每次使k-1个数字为1，在有小于k-1个数字不为1的情况下使剩下的数字为1.代码如下：
展开全文
牛客算法周周练5 C 序列最小化 题目大意 给定 1 ~ n 的一个排列, 每次选择序列中 k 个连续的数字，全部替换为其中最小的数. 询问最少的次数. 分析 应该不难想到, 最终, 序列中的每一个数都将变为 1. 那么就从 1 的位置开始, 连续选 k 个数, 变为 1 即可.不过, 操作完后,
展开全文
贪心：首先注意题目说这个数列肯定是1-n的一个全排列。那么说明这个数列一开始的数都是1~n中的,并且最小的是1.那么,很显然最后的结果肯定全部为1.因为想要替换为全部都一样,且每次替换都是在变小,那么最后肯定是全部为1才能实现.所以我们直接用1去替换更优.为什么呢？因为如果用其他的数去替换,最终还是
展开全文
C、序列最小化 因为是一个全排列数组，最终一定全部换成1，那么这个过程中替换1以外的数字都是多花功夫，记录全部换成1最少的步骤。 方法一：比较朴素的方法记录到1出现的位置，枚举最开始更新1的区间，再计算起始区间左边+右边需要的次数，更新答案取最小值即可。这种方法有一个好处，就是如果你采取这个方法，
展开全文
题目将n个数的某一种排列，经过若干次操作，变成同一个数。想要使操作数最少，那么第一次操作k个数，然后从第二次起操作额外的（k-1）个数和一个已经被操作过的数就可以了。实际操作次数跟数组里面的排列是怎么样的并没有关系，所以只是输入就好了。详细看代码。 #include <bits/stdc++.
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
