时间轴

2025-11-03

init

题目：

P1578 使绳子变成彩色的最短时间

https://leetcode.cn/problems/minimum-time-to-make-rope-colorful/description/?envType=daily-question&envId=2025-11-03

贪心，如果一组气球相同那么把这组需要最大时间的留下，其他都移除。

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
#include <string>
#include <vector>
#include <algorithm>

using std::string;
using std::vector;

class Solution {
    public:
	int minCost(string colors, vector<int> &neededTime)
	{
		int i = 0, j=1, n = colors.size();
		int res = 0;
		int max_time;
		int total;
		while (j < n) {
			j = i + 1;
			total = neededTime[i];
			max_time = neededTime[i];
			while (colors[i] == colors[j]) {
				max_time = std::max(neededTime[j], max_time);
				total += neededTime[j];
				j++;
			}
			if (total == neededTime[i]) {
			    i++;
			} else {
				res += total - max_time;
				i = j;
			}
		}

		return res;
	}
};

int main()
{
	Solution s;
	string colors = "abaac";
	vector<int> neededTime = { 1,2,3,4,5 };
	s.minCost(colors, neededTime);
}