1508: 墙的重建

内存限制:128 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:6 通过:4

题目描述

Blotch修建了一面墙。

墙由 N 个部分构成,从左到右依次编号 1 到 N。

由于他修建的十分匆忙,墙的各个部分高度可能并不相同。

第 i 个部分墙体的高度用 Ai 来表示。

Blotch想要通过重建部分墙面,从而对墙进行修整。

他可以将任意部分的墙面重修为任意高度。

重修完成之后,如果满足 Ai≠Ai+1的 i (1≤i<N)的数量不超过 k,他将会十分高兴。

在满足能够使得Blotch十分高兴的前提下,最少需要重建多少部分墙面?  

输入格式

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

每组测试数据共两行,第一行包含整数 N 和 k。

第二行包含 N 个整数,其中第 i 个整数表示第 i 部分墙体的高度 Ai。



输出格式

每组数据输出一个结果,每个结果占一行。

结果表示为“Case #x: y”,其中x是组别编号(从1开始),y为最少需要重建的墙面数量。

数据范围

1≤T≤100,
1≤Ai≤100,
0≤k≤N,
2≤N≤100

输入样例:

4
8 2
300 100 300 300 200 100 800 500
5 3
100 100 100 100 3
7 3
10 20 40 10 10 30 30
10 2
30 30 60 60 90 90 60 60 30 30

输出样例:

Case #1: 3 
Case #2: 0 
Case #3: 1 
Case #4: 2 

样例解释

在第一个示例中,有N = 8个墙段,如果相邻段之间的高度变化最多为K = 2,则Blotch会很高兴。他可以:

  • 重建墙壁的第二部分,使其高度为300,
  • 重建墙壁的第六部分,使其高度为200,
  • 重建墙壁的第八部分,使其高度为800。

这将产生一面各部分高度分别为300、300、300、300、200、200、800、800的墙,这使Blotch感到高兴。

在第二个示例中,有N = 5个墙段,并且如果相邻段之间的高度变化最多为K = 3,则Blotch将很高兴。 Blotch已经对这堵墙感到满意,因此他不需要重建任何部分。

在第三个示例中,有N = 7个墙段,并且如果相邻段之间的高度变化最多为K = 3,则Blotch将很高兴。他可以:

  • 重建墙的第二部分,使其高度为10。

这将产生一面各部分高度分别为10、10、40、10、10、30、30的墙,这使Blotch感到高兴。

在第四个示例中,有N = 10个墙段,并且如果相邻段之间的高度变化最多为K = 2,则Blotch将很高兴。他可以:

  • 重建墙壁的第五部分,使其高度为60,
  • 重建墙壁的第六部分,使其高度为60。

这将产生一面各部分高度分别为30、30、60、60、60、60、60、60、60、30、30的墙,这使Blotch感到高兴。

输入样例 复制

4
8 2
300 100 300 300 200 100 800 500
5 3
100 100 100 100 3
7 3
10 20 40 10 10 30 30
10 2
30 30 60 60 90 90 60 60 30 30

输出样例 复制

Case #1: 3
Case #2: 0
Case #3: 1
Case #4: 2

分类标签