2391. 收集垃圾的最少总时间

给你一个下标从 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 分钟收拾完所有的纸垃圾。
   收拾玻璃的垃圾车：
5. 收拾房子 0 的玻璃垃圾
6. 从房子 0 行驶到房子 1
7. 从房子 1 行驶到房子 2
8. 收拾房子 2 的玻璃垃圾
9. 从房子 2 行驶到房子 3
10. 收拾房子 3 的玻璃垃圾
    收拾玻璃的垃圾车总共花费 13 分钟收拾完所有的玻璃垃圾。
    由于没有金属垃圾，收拾金属的垃圾车不需要花费任何时间。
    所以总共花费 8 + 13 = 21 分钟收拾完所有垃圾。
    示例 2：

输入：garbage = ["MMM","PGM","GP"], travel = [3,10]
输出：37
解释：
收拾金属的垃圾车花费 7 分钟收拾完所有的金属垃圾。
收拾纸的垃圾车花费 15 分钟收拾完所有的纸垃圾。
收拾玻璃的垃圾车花费 15 分钟收拾完所有的玻璃垃圾。
总共花费 7 + 15 + 15 = 37 分钟收拾完所有的垃圾。

提示：

2 <= garbage.length <= 105
garbage[i] 只包含字母 'M' ，'P' 和 'G' 。
1 <= garbage[i].length <= 10
travel.length == garbage.length - 1
1 <= travel[i] <= 100

解题过程：
首先肯定是推导一下样例1

样例一是[G,P,GP,GG],[2,4,3]

思路一：看到题目中说的一辆垃圾车在动或者处理的情况下，其他车不允许移动。那么我就想到，每辆车是相对独立的，就是我可以把三辆车分开算。我们先看车G，遍历一遍每个房子有没有垃圾G，有的话就加上走的路程所需的时间，和房子里垃圾G的数量。没有的话先记录走过来路程所需的时间，为之后有垃圾G做准备。其他垃圾M车，垃圾P车同理

思路二：
通过思路一我想到，因为垃圾处理是固定的1分钟，所以我们可以直接把所以字符的垃圾数量加上，因为不论是G,P,M他们的处理时间都是1分钟，所以处理这么多垃圾的时间肯定就是数量，这个无关于那种垃圾。
然后就是路程问题，我们只需要从后往前看，每种垃圾都是什么时候出现的。加上前缀和就行了。

这两种方法都能解决问题。思路一比较正常的解题方法。思路二是在思路一的基础上进行扩展的方法。反正不管黑猫白猫能抓住耗子的猫就是好猫。能解决问题就行。就当扩展一下思路了。

///思路一
func garbageCollection(garbage []string, travel []int) int {
   
    l:=len(garbage)
    ans:=0
    m:=0
    p:=0
    g:=0
    for i:=0;i<l;i++{
   
        ll:=len(garbage[i])
        for j:=0;j<ll;j++{
   
            if garbage[i][j]=='M'{
   
                ans+=1
                ans+=m
                m=0
            }else if garbage[i][j]=='P'{
   
                ans+=1
                ans+=p
                p=0
            }else if garbage[i][j]=='G'{
   
                ans+=1
                ans+=g
                g=0
            }
        }
        if i!=l-1{
   
            m+=travel[i]
            p+=travel[i]
            g+=travel[i]
        }
    }
    return ans
}

//思路二
func garbageCollection(garbage []string, travel []int) int {
   
    l:=len(garbage)
    ans:=0
    a:=make([]int,l-1)
    for i:=0;i<l-1;i++{
   
        a[i]=travel[i]
        if i!=0{
   
            a[i]+=a[i-1]
        }
    }
    fmt.Println(a)
    p:=0
    m:=0
    g:=0
    for i:=l-1;i>=0;i--{
   
        ll:=len(garbage[i])
        ans+=ll
        if p==1&&m==1&&g==1{
   
            continue
        }
        for j:=0;j<ll;j++{
   
            if p==0&&garbage[i][j]=='P'&&i!=0{
   
                ans+=a[i-1]
                p=1
            }
            if m==0&&garbage[i][j]=='M'&&i!=0{
   
                ans+=a[i-1]
                m=1
            }
            if g==0&&garbage[i][j]=='G'&&i!=0{
   
                ans+=a[i-1]
                g=1
            }
        }
    }
    return ans
}