Halo

A magic place for coding

0%

小红与粉刷匠

Problem

  小红遇到了一名粉刷匠。这名粉刷匠有三种颜料,分别是红、黄、蓝。为了方便, 这三种颜料分别命名为 A,B,C。

  现在,粉刷匠正在粉刷一面长度为3n 的墙壁。粉刷完之后,三种颜料的数目都相同。由于小红一不小心踢到了颜料桶,使得这面墙的每个地方都被染上了三种颜料中的其中一种,这很让粉刷匠头疼。

  粉刷匠每次可以选择一段连续的墙壁进行粉刷,即全部粉刷上同一种颜色(A,B,C 三种中的其中一种)。粉刷匠想知道,他最少需要多少次粉刷才能使得三种颜料的数目都相同?

Example 1:

1
2
3
4
5
6
7
8
Input
ABACBC

Output
0

Explanation
A、B、C的数目都是2,不需要粉刷

Example 2:

1
2
3
4
5
6
7
8
Input
AAABBBBAC

Output
1

Explanation
把区间[6, 8]全部刷成C

Example 3:

1
2
3
4
5
6
7
8
Input
CAACBCBCC

Output
2

Explanation
先把区间[3, 3]粉刷成B,得到CAABBCBCC。然后把区间[8, 8]粉刷成为A

Analysis

  这道题目一开始很难入手,因为颜色不一定是连续的,所以选择哪块区间和刷哪种颜色都不知道。但是有一个很重要的信息就是,我们知道最后每种颜色有多少块。无非有三种情况:

  1. 当三种颜色的数量都一样,那么直接就是答案了,返回0;
  2. 当一种颜色多了,其余两种颜色少了,那必定要刷超过2次,因为数量少的每种颜色至少各刷一次去增加数量;
  3. 当两种颜色多了,一种颜色少了,至少刷一次去增加数量少的颜色。

  然后我们根据题目的例子发现,刚好对应了上面的三种情况,答案不超过2,这似乎是一个规律。于是我们可以思考下刷的次数到底有没有可能超过2呢?假设我刷超过2次,那么减少的颜色的种类就超过2种,因为每一次刷至少减少一种颜色。那么减少的颜色超过2种说明三种颜色的数量都减少了,这个是不符合题意的,所以可以得到刷的次数最多就是2。

  有了这个规律就很好做了,我们只需要统计出每种颜色的数字,然后把多余的颜色找出来。再用滑动窗口去找是否满足有多余颜色的子串,如果有,说明刷一次就能解决,如果没有,说明要刷2次。

Solution

  无。


Code

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <string>
using namespace std;

int minimumOperation(string str) {
int n = str.size();
int count[3] = {0};

for (char ch: str) {
++count[ch - 'A'];
}

int need[3] = {0};
int m[3] = {0};
int needValid = 0;
for (int i = 0; i < 3; ++i) {
if (count[i] > n / 3) {
need[i] = count[i] - n / 3;
++needValid;
}
}

if (needValid == 0) {
return 0;
}
if (needValid == 1) {
return 2;
}

int left = 0, right = 0;
int valid = 0;
while (right < n) {
char ch = str[right++];
if (need[ch - 'A'] > 0) {
++m[ch - 'A'];
if (m[ch - 'A'] == need[ch - 'A']) {
++valid;
}
}
if (valid == needValid) {
// cout << left << " " << right << endl;
return 1;
}

while (m[ch - 'A'] > need[ch - 'A']) {
ch = str[left++];
if (m[ch - 'A'] == need[ch - 'A']) {
--valid;
}
--m[ch - 'A'];
}
}
return 2;
}

int main() {
string str = "";
cin >> str;
cout << minimumOperation(str) << endl;
return 0;
}

Summary

  这道题目难度不小,首先需要通过找规律的方法来确定最大的粉刷次数是2,然后分析出不同情况的刷法,最后利用滑动窗口来寻找是否存在一次粉刷的情况,可谓是结合了分析和coding skill,是一道难得的好题!这道题目的分享到这里,感谢你的支持!

Welcome to my other publishing channels