[Запись вопросов по жадному алгоритму] 134. Заправка

[Запись вопросов по жадному алгоритму] 134. Заправка.

2024-07-12

Описание вопроса

Первоначальный ответ

Идеи все в комментариях, времени не хватит.

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        /* 首先出发站startIndex获得的汽油要大于前往下一站要消耗的汽油
        *  也就是：gas[startIndex] >= cost[startIndex]
        *  将计算公式写出来就是：例如从startIndex = 3出发
        *  ((((0 + gas[3] - cost[3]) + gas[4] - cost[4]) + gas[0] - cost[0]) + gas[1] - cost [1]) + gas[2] - cost[2] = 0可以返回
        *  但是还有条件：每一次括号中的计算结果也要大于0
        */ 
        vector<int> v1(gas.size(), 0);
        for(int i = 0; i < gas.size(); i++){
            v1[i] = gas[i] - cost[i];
        }
        /* 上面的计算公式就变成了((((0 + v1[3]) + v1[4]) + v1[0]) + v1[1]) + v1[2] = 0
        *  那么下面我们根据条件“每一次括号中的计算结果也要大于0”来进行判断
        */
        
        // 首先判断整体和如果小于0，那么肯定不能环绕一圈
        if(accumulate(v1.begin(), v1.end(), 0) < 0) return -1;
        int result = -1;
        for(int i = 0; i < gas.size(); i++){
            // 找到第一个汽油大于0的加油站
            if(v1[i] < 0) continue;
            int num = gas.size();
            int k = i;
            int sum = v1[k];
            while(num--){
                if(k == gas.size() - 1){
                    sum += v1[0];
                    k = 0;
                }
                else sum += v1[++k];
                if(sum < 0) break;
            }
            if(sum >= 0) result = i;
        }
        return result;
    }
};
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

Жадный анализ версий

Я давно не решал задачи по жадному алгоритму и даже не помню, как делать орз...

Прежде всего, ограничением этого вопроса является то, что чистый объем остаточной нефти каждой станции должен быть больше или равен 0, то естьrest[i] = gas[i] - cost[i] >= 0。

Затем я начинаю накапливать с индекса 0rest[i], сумма которых записывается какcurSum,один разcurSumменьше 0, это означает, что от 0 доiВ пределах этого интервала, независимо от того, какой сайт выбран в качестве исходного, пункт назначенияiу всех кончится топливо, тогда мы сможем выбратьi+1Начните перерасчет в качестве отправной точки.

Подводя итог приведенному выше анализу:
Локальный оптимум:curSumЕсли оно меньше 0, для выполнения условия начальная позиция должна быть не меньше i+1.
Глобальный оптимум: вы можете найти стартовую позицию, на которой можно пробежать один круг.

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int curSum = 0;
        int totalSum = 0;
        int start = 0;
        for(int i = 0; i < gas.size(); i++){
            curSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];
            if(curSum < 0){
                start = i + 1;
                curSum = 0;
            }
        }
        if(totalSum < 0) return -1;
        return start;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Обмен технологиями