New Online Judge 主页 问题 来源/分类 竞赛&作业 状态 排名 常见问答
登录 注册

2139: K级冒泡排序

内存限制：256 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：9 通过：5
提交提交记录统计

题目描述

小明提出了一个 k 级冒泡排序算法，对于一个长度为 n 的数组 a ，给定数字 k：
在每分钟内：
  • 对第 1 个数字到第 k 个数字进行排序；
  • 对第 2 个数字到第 k+1 个数字进行排序；
  • 对第 3 个数字到第 k+2 个数字进行排序；
  • ...
  • 对第 n-k+1 个数字到第 n 个数字进行排序。
例如 k=2 就是最传统的冒泡排序算法。
小明想知道最少花费几分钟可以将数组 a 排好序。

输入格式

输入第一行包含两个整数 n, k。2 ≤ k ＜ n ≤ 2500。
第二行包含 n 个整数表示数组 a ，0≤a[i]≤1,000,000,000。

输出格式

输出一个数字表示答案。

输入样例 复制 

样例1：
5 2
3 4 1 5 2

样例2：
8 3
60 8 27 7 68 41 53 44

样例3：
6 3
3 2 4 2 3 1

输出样例 复制 

样例1：
3

样例2：
2

样例3：
3

数据范围与提示

来源：2022.BAPC