day 34(补)贪心（3）

day34
代码随想录
2024.1.3

1. 1005K次取反后最大化的数组和
这道题还是很容易想的，将负数从小至大变为正数，保证再K次内，每次k–；如果，经过这样一轮后，K还是大于0，此时，数组全部为正，已经最大了，如果此时的k为偶数，那就不用管，如果是奇数，表示必须有一个数变成负数，在排序，最小的变成负数就好

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int result = 0;
        int num = k;
        for(int i=0;i<nums.size();i++){
            if(nums[i]<0 && num>0){
                nums[i] *= -1;
                num--;
            }
        }
        if(num%2==1){
            sort(nums.begin(), nums.end());
            nums[0] *= -1;
        }
        for(auto nu:nums)
            result += nu;
        return result;
    }
};

2. 134加油站
这道题方法很巧妙，根据加油量和耗油量，算出差值，也就是剩油量，剩油量之和代表了能不能跑通一圈，如果整体和小于0，那是一定不能跑通的。然后就是确定位置，根据局部之和判断，如果局部之和小于0，说明，该路之前点位都不通，至少要在拒绝点的下一个点开始，以为类推，最后将起始点确定。

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) {   // 当前累加rest[i]和 curSum一旦小于0
                start = i + 1;  // 起始位置更新为i+1
                curSum = 0;     // curSum从0开始
            }
        }
        if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了
        return start;
    }
};

3. 135分发糖果
这道题同样是，没做过的话，很难想到思路。代码很好写，主要是思路。
题目要求相邻最高，这就牵扯到左右对比，因此要分两步分别处理，先处理左，然后右。或者顺序相反。但注意，两次遍历方向是有说法的，比如，如果先处理右大于左，那么每次对比，就要保证左边是不变的，也就是已经处理过的，因此遍历顺序正常从左往右，但是第二步处理左大于右，此时如果正常从左往右遍历，每次i跟i+1对比，但是，因为往右处理，i+1下次值有可能发生变化，那么i的对比就不对了，因此要从右往左，保证右边已经处理过了即可。

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> res(ratings.size(), 1);
        int result = 0;
        for(int i=1;i<ratings.size();i++){
            //右比左大
            if(ratings[i]>ratings[i-1])
                res[i] = res[i-1]+1;
        }
        for(int i=ratings.size()-2;i>-1;i--){
            //左比右大
            if(ratings[i]>ratings[i+1] && res[i]<res[i+1])
                res[i] = res[i+1]+1;
            if(ratings[i]>ratings[i+1] && res[i]==res[i+1])
                res[i] = res[i+1]+1;
            if(ratings[i]>ratings[i+1] && res[i]>res[i+1])
                continue;
        }
        for(auto n:res)
            result += n;
        return result;
    }
};