#B. 元旦硬币

    传统题 1000ms 256MiB

元旦硬币

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

在一实的元旦晚会中,谢老师给图灵班的学生出了一道智力游戏:在地上有nn个篮子,每个篮子里都有若干个硬币,第ii个篮子硬币的数量用aia_i来表示,那nn个篮子的硬币数量分别为 a1,a2,,ana_1,a_2,…,a_n。谢老师给出了一些操作,可以用一系列的操作,让每一个篮子里硬币的数量都相等。

具体操作如下:

  1. nn个篮子中选取连续的一段区域,并且选取的区域中篮子个数不超过kk个。
  2. 对于选中的一段区域里,可以对区域中每一个篮子重新往里面添加或者去掉一些硬币,当然也可以保持篮子里原来的硬币数量不变。注意对于每一个篮子的操作是独立的。

现在谢老师想让图灵班的学生们通过这一系列的操作,让每个篮子里面的硬币数量都相等,最少需要多少操作?

第一次完成任务的学生会得到丰厚的奖品,现在你很想拿到这个奖品,于是你决定用编程来完成这个任务。

输入格式

第一行包含整数 TT,表示共有 TT 组测试数据。

每组数据第一行包含两个整数 nnkk

第二行包含 nn个空格隔开的整数 a1,a2,,ana_1,a_2,…,a_n

输出格式

每组数据输出一行结果,表示最少需要进行的操作次数。

数据范围

对于前三个测试点,1kn101≤k≤n≤10。 对于全部测试点,1T104,1kn105,1ai1001≤T≤10^4,1≤k≤n≤10^5,1≤a_i≤100,保证所有 TTnn 的和不超过10510^5

输入样例:

3
10 2
1 1 2 2 1 1 2 2 2 1
7 1
1 2 3 4 5 6 7
10 3
1 3 3 3 3 1 2 1 3 3

输出样例:

3
6
2

样例解释

样例数据1:

121 \sim 2这一段选取成一个区域,往该区域里面所有篮子添加硬币使每个篮子硬币数量变为 22

此时所有的篮子硬币数量为:

2 2 2 2 1 1 2 2 2 1

再将 454 \sim 5 这一段区域里的篮子里的硬币添加硬币使每个篮子硬币数量变为 22

此时所有的篮子硬币数量为:

2 2 2 2 2 2 2 2 2 1

最后将 1010 这一段区域里的篮子里的硬币添加硬币使每个篮子硬币数量变为 22

2 2 2 2 2 2 2 2 2 2

共操作 33

样例数据2:

选取223344556677这六段区域的篮子硬币进行修改。

最终所有篮子的硬币数量为:

1 1 1 1 1 1 1

共操作 66

样例数据3: 选取1 1686\sim8 这两段区域的篮子硬币进行修改。

最终所有篮子的硬币数量为:

3 3 3 3 3 3 3 3 3 3

共操作 22

test

未参加
状态
已结束
规则
OI
题目
3
开始于
2024-4-13 15:45
结束于
2024-4-13 17:45
持续时间
2 小时
主持人
参赛人数
1