蓝桥oj3272小蓝的漆房

问题描述

小蓝是一位有名的漆匠，他的朋友小桥有一个漆房，里面有一条长长的走廊，走廊两旁有许多相邻的房子，每间房子最初被涂上了一种颜色。

小桥来找小蓝，想让他把整个走廊都涂成同一个颜色。小蓝告诉小桥，他每天只能涂一段长度为 k 的区间。对于每个区间，他可以选择将其中的房子重新涂上任何一种颜色，或者保持原来的颜色不变。

小桥想知道小蓝至少要涂几天，才能让整个走廊变得美丽。

请帮助小桥解决这个问题。

输入格式

第一行包含一个整数 t（1≤100），表示测试用例的数量。

每个测试用例的第一行包含两个整数 n 和 k（1≤k≤n≤104），第二行包含 nn 个整数 a1,a2,??,an?（1≤ai≤60），分别表示每个房子最初的颜色。

保证所有测试用例中 n 的总和不超过 104。

输出格式

对于每个测试用例，输出一个整数，表示小蓝需要涂漆的最少天数。

样例输入

2
5 2
1 1 2 2 1
6 2
1 2 2 3 3 3

样例输出

1
2

我的分析

题目中a[i]<=60,即房子最多有60种，枚举最后的统一颜色，再比较得到最小的涂漆次数即可

我的代码

#include <iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e4 + 10;
int a[N];
int main()
{
	// 请在此输入您的代码
	int t; cin >> t;//测试用例数量
	for (int i = 1; i <= t; i++)
	{
		int n, k; cin >> n >> k;//n个房子 每天涂k个
		for (int i = 1; i <= n; i++)cin >> a[i];
		int mins = 1e5;

		for (int i = 1; i <= 60; i++)//全部涂成i
		{
			int ans = 0;
			for (int j = 1; j <= n;)
			{
				if (a[j] == i)j++;
				else j += k, ans++;//ans是涂了几天
			}
			mins = min(ans, mins);
		}
		cout << mins << endl;
	}
	
	return 0;
}