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

发布时间:2024年01月15日

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
输入

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. 对于每个测试用例,代码读入两个整数nk,分别表示房子的数量和每天可涂漆的区间长度。

  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是不同颜色的数量。在最坏的情况下,这个算法可能会有些慢,但考虑到题目中给出的最大n10^4和颜色总数不超过60,这个方法在实践中是可行的。

文章来源:https://blog.csdn.net/weixin_74774974/article/details/135610818
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。