枚举 小蓝的漆房

题目

思路

核心思想是枚举
首先利用set记录每一种颜色
然后依次从set取出一种颜色作为targetColor，遍历房子
如果当前房子的颜色和targetColor不相同，就以当前房子为起点，往后长度为k的区间都涂成targetColor，并且需要的天数递增1
否则就一直向下遍历直到所有房子遍历完

代码

#include 
#define MAX 1e5;
using namespace std;
int main() {
    int t;
    scanf("%d", &t);
    for(int i = 0; i < t; i++) {
        int n, k;
        scanf("%d %d", &n, &k);
        set mySet;
        vector myVector;
        for(int i = 0; i < n; i++) {
            int data;
            scanf("%d", &data);
            mySet.insert(data);
            myVector.push_back(data);
        }
        int minDay = MAX;
        for(const auto& targetColor : mySet) {
            // printf("target color is %d\n", targetColor);
            int day = 0;
            int i = 0; 
            while(i < n) {
                // printf("current house id is %d\n", i);
                // printf("current color of hourse is %d\n", myVector[i]);
                if(myVector[i] != targetColor) {
                    i = i + k;
                    day++;
                }
                else {
                    i++;
                }
            }
            if(day < minDay) {
                minDay = day;
            }
        }
        printf("%d\n", minDay);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41