传送锚点：https://leetcode.cn/problems/minimum-amount-of-time-to-collect-garbage/description/
给你一个下标从 0 开始的字符串数组 garbage ，其中 garbage[i] 表示第 i 个房子的垃圾集合。garbage[i] 只包含字符 'M' ，'P' 和 'G' ，但可能包含多个相同字符，每个字符分别表示一单位的金属、纸和玻璃。垃圾车收拾 一 单位的任何一种垃圾都需要花费 1 分钟。
同时给你一个下标从 0 开始的整数数组 travel ，其中 travel[i] 是垃圾车从房子 i 行驶到房子 i + 1 需要的分钟数。
城市里总共有三辆垃圾车，分别收拾三种垃圾。每辆垃圾车都从房子 0 出发，按顺序 到达每一栋房子。但它们 不是必须 到达所有的房子。
任何时刻只有 一辆 垃圾车处在使用状态。当一辆垃圾车在行驶或者收拾垃圾的时候，另外两辆车 不能 做任何事情。
请你返回收拾完所有垃圾需要花费的 最少 总分钟数。
示例 1：
输入：garbage = ["G","P","GP","GG"], travel = [2,4,3]
输出：21
解释：
收拾纸的垃圾车：
1. 从房子 0 行驶到房子 1
2. 收拾房子 1 的纸垃圾
3. 从房子 1 行驶到房子 2
4. 收拾房子 2 的纸垃圾
收拾纸的垃圾车总共花费 8 分钟收拾完所有的纸垃圾。
收拾玻璃的垃圾车：
1. 收拾房子 0 的玻璃垃圾
2. 从房子 0 行驶到房子 1
3. 从房子 1 行驶到房子 2
4. 收拾房子 2 的玻璃垃圾
5. 从房子 2 行驶到房子 3
6. 收拾房子 3 的玻璃垃圾
收拾玻璃的垃圾车总共花费 13 分钟收拾完所有的玻璃垃圾。
由于没有金属垃圾，收拾金属的垃圾车不需要花费任何时间。
所以总共花费 8 + 13 = 21 分钟收拾完所有垃圾。
示例 2：
输入：garbage = ["MMM","PGM","GP"], travel = [3,10]
输出：37
解释：
收拾金属的垃圾车花费 7 分钟收拾完所有的金属垃圾。
收拾纸的垃圾车花费 15 分钟收拾完所有的纸垃圾。
收拾玻璃的垃圾车花费 15 分钟收拾完所有的玻璃垃圾。
总共花费 7 + 15 + 15 = 37 分钟收拾完所有的垃圾。
思路
时间分为垃圾车到每间房子的时间和垃圾车处理垃圾的时间
Code 1
class Solution {
public:
int garbageCollection(vector<string>& garbage, vector<int>& travel) {
map<char,int> mp;//记录垃圾离起始点最远位置
mp['W'] = 0, mp['G'] = 0, mp['P'] = 0;
int time_pick = 0;//捡垃圾的时间
for(int i = 0; i < garbage.size(); i++){//遍历每间房子所含的垃圾种类
time_pick += garbage[i].size();
for(char c : {'G', 'P', 'M'}){
if(garbage[i].find(c) != string::npos){
mp[c] = i;
}
}
}
int time_arrive = 0;
for(auto pair : mp){
int pos = pair.second;//垃圾最后出现的位置
time_arrive += accumulate(travel.begin(), travel.begin() + pos, 0 );
}
return time_pick + time_arrive;
}
};
Code 2
class Solution {
public:
int garbageCollection(vector<string>& garbage, vector<int>& travel) {
//灵神的一次遍历,方法太nice了,通过从最远房子开始计算贡献值
//路段数比房子数少1
unordered_set<char> visit;
int ans = garbage[0].size();
for(int i = garbage.size() - 1; i; i--){
auto &g = garbage[i];
visit.insert(g.begin(), g.end());
ans += g.size() + visit.size() * travel[i-1];
}
return ans;
}
};