首页 > 试题广场 >

序列最小化

[编程题]序列最小化
  • 热度指数：1833 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

有一个长度为N的序列。一开始，这个序列是1, 2, 3,... n - 1, n的一个排列。

对这个序列，可以进行如下的操作：

每次选择序列中k个连续的数字，然后用这k个数字中最小的数字替换这k个数字中的每个数字。

我们希望进行了若干次操作后，序列中的每个数字都相等。请你找出需要操作的最少次数。


输入描述:
第一行：两个数字n, k，含义如题，满足2 <= k <= n <= 105；
第二行：n个数字，是1, 2, 3,...n的一个排列。


输出描述:
一个整数，表示最少的次数。
示例1

输入

2 2
2 1

输出

1
示例2

输入

4 3
1 2 3 4

输出

2
算法知识视频讲解
添加回答
念、往昔╮头像 念、往昔╮
方法1：
序列的最终结果为一个数，那么长度为n的序列有n-1个数字需要改变；每次取k个数字，则最多有k-1个数字需要改变，所以次数为(n-1)/(k-1)向上取整。

#include<bits/stdc++.h>

using namespace std;

int main(){

int n,k;

while(cin>>n>>k){

for(int i = 0;i<n;i++){

int x;

cin>>x;

}

cout<<ceil((double)(n-1)/(k-1))<<endl;

}

system("pause");

return 0;

}

方法2：
第一步：从n个数字中不重复的取k个数字，则可取n/k次，剩余（n/k+n%k）个数字不同；
第二步：从n/k+n%k个数中取k个数字，重复第一步，直到剩余数字<=k个。
#include<iostream>
#include <string>
usingnamespacestd;
intmain()
{
intn,k;
intcycle=0,num=0;
string s;
cin>>n>>k;
getline(cin,s);
while((n>k))
{
cycle=n/k;
n=cycle+n%k;
num+=cycle;
}
num++;
cout<<num;
}

编辑于 2018-08-24 16:35:11 回复(0)
WAK头像 WAK

考虑极限情况，除了最左边和最右边以外，中间每个相邻的k个公用一个最小值。除去第一个，剩下的n-1个，除（k-1），然后向上取整，就是最少的次数。

答案：

#include<bits/stdc++.h>

using namespace std;

int main(){

    int n,k;

    while(cin>>n>>k){

        for(int i = 0;i<n;i++){

            int x;

            cin>>x;

        }

        cout<<ceil((double)(n-1)/(k-1))<<endl;

    }

    system("pause");

    return 0;

}

发表于 2018-07-20 20:02:47 回复(0)
素衣_头像 素衣_
import java.util.Scanner;
public class Main { 
  public static void main(String[] args) {
   int result = 0;
         Scanner sc = new Scanner(System.in);
         int  n = sc.nextInt();
         int  l = sc.nextInt();         
         if(n==l){
             System.out.println(1);
         }
         else{
             result = (n-l)/(l-1) +1;
             if((n-l)%(l-1)>0) {
                    result++;
                }          
            System.out.println(result);
         }      
     }  
}

发表于 2018-08-01 14:49:12 回复(0)
jachy头像 jachy 
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, k;
    cin >> n >> k;
    int arr[n];
    for(int i = 0; i < n; i++) cin >> arr[i];   
    int count = 0;
    while(n > k){ n -= k-1; count++; }
    cout << count+1 << endl;
    return 0;
}
编辑于 2018-08-07 11:38:56 回复(0)
海阔天空126头像 海阔天空126
# 答案为 （n-1）/(k-1) 若由余数则就需要 +1，没想到就AC了。
应该是题目测试没有考虑比较复杂的情况～～o(╯□╰)o 
n,k = map(int,input().split())
print(round((n-1)/(k-1)+0.49))
发表于 2018-07-31 15:46:43 回复(0)
C/C++
lang丶头像 lang丶

#include<stdio.h>
int main()
{
int n,k;
scanf("%d %d",&n,&k);
int time=0,sum,temp;
while(n>=k)
{
sum=n/k;
temp=n%k;
time+=sum;
n=sum+temp;
}
if(temp) printf("%d",time+1);
else printf("%d",time);
return 0;
}

编辑于 2018-07-31 17:17:50 回复(0)
Demon=)头像 Demon=) 
import java.util.Scanner;
public class Main {  public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int k = scan.nextInt();
        int count = 1;
        Integer[] num = new Integer[n];
        for(int i = 0; i < n;i++)  num[i] = scan.nextInt();
        int len = num.length;
        while(len > k) {  len -= (k - 1);  count += 1;
        }
        
        System.out.println(count);

    }
}
编辑于 2018-07-26 08:58:44 回复(0)
伊涅斯塔头像 伊涅斯塔
#include<iostream>
#include<string>
#include<math.h>
using namespace std;
intmain()
{
intn, k, T;
cin >> n >> k;
int*arr = newint[n];
for(inti = 0; i < n; i++) {
cin >> arr[i];
}
T = (n - 1) / (k - 1);
if((n - 1) % (k - 1) != 0) T++;
cout << T << endl;
delete[] arr;
return0;
}
编辑于 2018-07-23 16:04:27 回复(1)
Roee头像 Roee 
import sys
import math
n, k = [int(x) for x in sys.stdin.readline().split()]
print int(math.ceil((n-1.0)/(k-1)))
发表于 2018-07-21 23:38:46 回复(3)
wbq9224头像 wbq9224 
import sys
import math
rvt = sys.stdin.readline().strip().split()
n = int(rvt[0])
k = int(rvt[1])
res = int(math.ceil((n - k) / (k - 1)) + 1)
print(res) 

发表于 2018-07-21 10:10:29 回复(1)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 数组 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 模拟 2018 数学 Java工程师 牛客
来自：【2018】牛客模考（...
上传者：小小
难度：
10条回答 5391浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号