蓝桥杯省赛无忧 编程4 小蓝的漆房

输入

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

输出

1
2

#include <bits/stdc++.h>
using namespace std;
int main() {
  int t; cin >> t;
  for (int i = 0, n, k; i < t; i++) {
      cin >> n >> k;
      vector<int> arr(n);
      unordered_set<int> s;
      for (int j = 0; j < n; j++) {
          cin >> arr[j];
          s.insert(arr[j]);  //一个集合，防止重复记录
      }
      int ans = INT_MAX;
      for(auto &x : s) {
          int cnt = 0;
          for(int j = 0; j < n; j++) {
              if(arr[j] == x) continue;  //如果当前颜色和我要涂的颜色一样，那么跳过
              cnt += 1;
              j += k - 1;   //否则将k区间内的颜色全部涂该种颜色，由于上面有j++,这里要-1
          }
          ans = min(ans, cnt);  //记录最小的就是答案
      }
      cout << ans << endl;
  }
  return 0;
}

这段代码的目的是解决前面提到的问题：计算小蓝至少需要多少天才能将走廊上所有房子涂成相同的颜色。代码逻辑如下：

1. 代码首先读入测试用例的个数t。

2. 对于每个测试用例，代码读入两个整数n和k，分别表示房子的数量和每天可涂漆的区间长度。

3. 接下来，代码初始化一个整型向量arr来存储每个房子的颜色，并创建一个集合s来存储所有独特的颜色（防止重复）。

4. 然后，代码使用一个嵌套循环来遍历集合s中的每一种颜色，检查如果将走廊上所有房子涂成该颜色，需要多少天。

5. 外层的for循环遍历集合s中的每一种颜色。对于每一种颜色：

   • 初始化变量cnt用来计数需要涂漆的天数。
   • 内层的for循环遍历整个走廊，检查每个房子的颜色：
     • 如果房子的颜色已经是当前考虑的颜色x，那么不执行任何操作。
     • 如果房子的颜色不是x，那么cnt加1（表示需要再涂一天），并且将索引j增加k-1，这是因为我们假设在这一天我们涂了从房子j开始的k长度的区间。

6. 在检查完所有房子之后，外层循环更新ans为所有尝试中的最小天数。

7. 最后，代码输出最小天数ans作为这个测试用例的答案。

代码使用了unordered_set来去除重复的颜色，并且使用INT_MAX来初始化ans确保能找到最小的天数。在每一轮的尝试中，代码都会尝试将整个走廊涂成一种颜色，并计算涂成该颜色所需的最小天数。代码利用了贪心的思路，即每次都会尽可能多地涂漆以减少涂漆的总天数。

这种方法的时间复杂度是O(nm)，其中n是房子的数量，m是不同颜色的数量。在最坏的情况下，这个算法可能会有些慢，但考虑到题目中给出的最大n为10^4和颜色总数不超过60，这个方法在实践中是可行的。