25.贪心算法3

加油站

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n=gas.size();
        vector<int> margin(n);
        for(int i=0;i<n;i++){
            margin[i]=gas[i]-cost[i];
        }
        int min=INT32_MAX;
        int count=0;
        int index=-1;
        for(int i=0;i<n;i++){
            if(margin[i]>=0){
                if(count<min){
                    index=i;
                    min=count;
                }
            }
            count+=margin[i];
        }
        count=0;
        if(index==-1)return -1;
        for(int i=0;i<n;i++){
            count+=margin[(i+index)%n];
            if(count<0)return -1;
        }
        
        return index;
    }
};

我的想法是从0开始累计，欠油最多且margin为正的地方，就是最好出发点；

因为如果从他前面出发，那到这里的时候，肯定比直接从这里出发的油少

从他后面出发，那不如加上这里，油更多一点

分发糖果

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n=ratings.size();
        int max_i=0;
        vector<int> alloc(n,1);
        for(int i=1;i<n;i++){
            if(ratings[i]>ratings[i-1]){
                alloc[i]=alloc[i-1]+1;
            }
        }
        for(int i=n-2;i>=0;i--){
            if(ratings[i]>ratings[i+1]){
                alloc[i]=alloc[i+1]+1>alloc[i]?alloc[i+1]+1:alloc[i];
            }
        }
        int res=0;
        for(int i=0;i<n;i++){
            res+=alloc[i];
        }
        return res;
    }
};

我之前的想法是只处理递增的，向正着看，再反着看

但有些细节没处理好，导致答案错了。

柠檬水找零

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int change[3]={0};
        for(int pay:bills){
            if(pay==5){
                change[0]++;
            }else if(pay==10){
                change[1]++;
                change[0]--;
            }else if(pay==20){
                if(change[1]){
                    change[1]--;
                    change[0]--;
                }else {
                    change[0]--;
                    change[0]--;
                    change[0]--;
                }
            }
            if(change[0]<0)return 0;
        }
        return 1;
    }
};

很简单

根据身高重建队列

class Solution {
public:
    static bool cmp(const vector<int> & a,const vector<int> & b){
        if(a[0]==b[0])return a[1]>b[1];
        return a[0]<b[0];
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        int n=people.size();
        sort(people.begin(),people.end(),cmp);
        vector<vector<int>> res(n,vector<int>(2,-1));
        for(int i=0;i<n;i++){
            int index=people[i][1];
            for(int j=0;j<=index;j++){
                if(res[j][0]!=-1)index++;
            }
            res[index]=people[i];
        }
        return res;
    }
};