Who's Studio.

HihoCoder#1135 - Magic Box

Word count: 340Reading time: 1 min
2016/05/10

题目

一个Magic Box，不断往里放三种颜色的球（红色R，黄色Y，蓝色B），一旦这三种球数目之差为x，y，z（无序），则所有球消失。给定一个放球的序列，求盒子中球最多时刻球的数目。
具体描述请见hihoCoder。

解题思路

直接暴力解。

时间复杂度

给定序列循环一遍，时间复杂度为N。

代码

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
#include <iostream>
#include <string>
#include <cmath>
using namespace std;

int maxLen(string seq, int x, int y, int z) {
	int max = 0;
	int len = 0;
	int r = 0, g = 0, b = 0;
	for (int i = 0; i < seq.size(); i++) {
		if (seq[i] == 'R')
			r++;
		else if (seq[i] == 'B')
			g++;
		else if (seq[i] == 'Y')
			b++;
		len++;
		if ((abs(r - g) == x && abs(g - b) == y && abs(b - r) == z) ||
			(abs(r - g) == x && abs(b - r) == y && abs(g - b) == z) ||
			(abs(g - b) == x && abs(r - g) == y && abs(b - r) == z) ||
			(abs(g - b) == x && abs(b - r) == y && abs(r - g) == z) ||
			(abs(b - r) == x && abs(g - b) == y && abs(r - g) == z) ||
			(abs(b - r) == x && abs(r - g) == y && abs(g - b) == z)) {
			r = 0;
			g = 0;
			b = 0;
			if (max < len)
				max = len;
			len = 0;
		}
	}

	if (max < len)
		max = len;

	return max;
}

int main() {
	int x = 0, y = 0, z = 0;
	string charSeq;
	cin >> x >> y >> z;
	cin >> charSeq;
	cout << maxLen(charSeq, x, y, z);
}

Author：Who Watson

Link：https://wangshenghu.github.io/2016/05/10/2016-05-10-hihocoder-magic-box/

Publish date：May 10th 2016, 12:03:52 pm

Update date：December 4th 2022, 5:04:47 pm

License：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 题目
  2. 2. 解题思路
  3. 3. 时间复杂度
  4. 4. 代码
Total : 56
2022
2016
test
笔记 算法 hihoCoder 实习经历 项目