Repainting Street

题意翻译

- 有一条街道，$n$ 栋房子排成一行，编号从 $1$ 到 $n$。每个房子的颜色为 $c_i$ ，工人每次可粉刷连续的 $k$ 个房子，求出将整条街刷成同一个颜色的最短的次数。 ------------ **【输入格式】** - 第一行输入整数 $t$ 为街道的条数，并且保证 $t$（$1 \leqslant t \leqslant {10}^4$） - 第二行输入两个整数 $n$ 和 $k$（$1 \leqslant k \leqslant n \leqslant {10}^5$） - 第三行输入房屋初始颜色 $c_i$（$1 \leqslant c_i \leqslant 100$） ------------ **【输出格式】** - 输出 $t$ 行，每行为每个街道粉刷需要的最少天数 Translated by [Seth](https://www.luogu.com.cn/user/358800).

题目描述

There is a street with $ n $ houses in a line, numbered from $ 1 $ to $ n $ . The house $ i $ is initially painted in color $ c_i $ . The street is considered beautiful if all houses are painted in the same color. Tom, the painter, is in charge of making the street beautiful. Tom's painting capacity is defined by an integer, let's call it $ k $ . On one day, Tom can do the following repainting process that consists of two steps: 1. He chooses two integers $ l $ and $ r $ such that $ 1 \le l \le r \le n $ and $ r - l + 1 = k $ . 2. For each house $ i $ such that $ l \le i \le r $ , he can either repaint it with any color he wants, or ignore it and let it keep its current color. Note that in the same day Tom can use different colors to repaint different houses. Tom wants to know the minimum number of days needed to repaint the street so that it becomes beautiful.

输入输出格式

输入格式

The first line of input contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ), the number of test cases. Description of test cases follows. In the first line of a test case description there are two integers $ n $ and $ k $ ( $ 1 \le k \le n \le 10^5 $ ). The second line contains $ n $ space-separated integers. The $ i $ -th of these integers represents $ c_i $ ( $ 1 \le c_i \le 100 $ ), the color which house $ i $ is initially painted in. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

输出格式

Print $ t $ lines, each with one integer: the minimum number of days Tom needs to make the street beautiful for each test case.

输入输出样例

输入样例 #1

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

输出样例 #1

3
6
2

说明

In the first test case Tom should paint houses 1 and 2 in the first day in color 2, houses 5 and 6 in the second day in color 2, and the last house in color 2 on the third day. In the second test case Tom can, for example, spend 6 days to paint houses 1, 2, 4, 5, 6, 7 in color 3. In the third test case Tom can paint the first house in the first day and houses 6, 7, and 8 in the second day in color 3.