caibirdme
commented
4 years ago Patching Array 由于要让正整数数组中的和覆盖1..n的所有数, 那么很显然如果要覆盖1, 数组中必然得存在1(大于1的数怎么相加都不可能等于1). 因此看如果数组没有1, 必然要添加一个1. 然后2同理, 虽然覆盖了1, 但是如果数组中没有2, 要么再添加一个1, 使得存在1+1=2, 或者直接添加一个2. 而我们要求最少添加多少数能覆盖所有1..n, 因此我们添加的数越大越好. 为啥呢? 假如我们1..k已经覆盖完了, k+1没被覆盖, 而数组中下一个数大于k+1. 此时我们可以添加1..k+1中的任何一个数都可以使得k+1被覆盖到. 但是直接添加k+1的话, 覆盖的值就达到了2k+1!比其它值能覆盖的长度都长.
Gas Station 这道题的几个贪心策略:
对于第二个, 其实证明也比较简单. 假设我们把所有gas[i]和cost[i]对应作差得到t[i], 当sum(t[i])>=0时, 我们一定能够找到一个点k, 使得sum(t[0]+..t[k]) <= 0 而sum(t[k+1]+..t[n]) >=0, 因此我们就可以选择k+1作为起点.
那么我们可以先假定从0号节点作为起点出发, 每次rest += gas[i]-cost[i], 当走到k时rest<0, 说明从0号点开始没法走一圈. 这时我们需要从1号点重新开始尝试吗? 答案是不需要, 因为当前rest = gas[0]-cost[0] + X < 0 ,X代表gas[1]-cost[1]+gas[2]-cost[2]+..gas[k]-cost[k]. 由于gas[0]>=cost[0], 相当于X+正数 < 0, 那么X肯定小于0, 所以从1..k-1号节点都没法走到k. 所以下一次我们直接以k节点为新起点即可.
这样总体复杂度就是O(n)
这道题需要能够大胆地在纸上做计算和证明, 如果0不行就想到下一次从1开始, 而不敢去证明的话, 这道题就很难做了.
很多时候包括DP的状态转移都是做决策, 做决策就需要证明这么选的最优的. DP的最优性很多时候很明显, 而贪心则需要多思考及推断证明