算法学习笔记-贪心算法总结2-阿里云开发者社区

下面继续总结贪心算法常用模型：

最大数

https://leetcode.cn/problems/largest-number/

问题叙述：给定一组非负整数，重新排列每个数的顺序，使之组成一个最大整数

思路：将数字都转为字符串并存储字符串数组，将字符串数组按拼接结果的字典序降序排序，如果排序后第一个元素为0，则其余元素也为0，直接返回0即可，否则，将排好序的字符串数组拼接为结果字符串

代码：

class Solution {
public:
    string largestNumber(vector<int>& nums) {
       vector<string> str;
       for(int num:nums) str.push_back(to_string(num)); 
        //按拼接结果的字典序降序排序
       sort(str.begin(),str.end(),[](const string &a,const string &b){
            return (a+b)>(b+a);
       });
       //排序后第一个元素是0，则其余元素也是0
       if(str[0]=="0") return "0";
       string res;
       for(string s:str) res+=s;
       return res;
    }
};

两地调度

https://leetcode.cn/problems/two-city-scheduling/

题目叙述：公司计划面试2n个人，给出二维数组cost[ac,bc]表示第i个人飞往a和飞往b的花费，返回每个人都飞到a,b中某座城市的最低费用，要求每个城市都有n人抵达。

思路：先假设所有人都去a地，然后记录每个人转去b地需要额外付出的钱，将额外付出钱最少的一半人改去b地。

代码：

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        //先假设都去a地，然后记录每个人改去b地需要额外付出的钱，
        //将额外付出最少的6个人改签去b地
        int sum=0;
        vector<int> diff(costs.size());
        for(int i=0;i<costs.size();i++){
            sum+=costs[i][0];
            diff[i]=costs[i][1]-costs[i][0];
        }
        sort(diff.begin(),diff.end());
        int n=diff.size()/2;
        for(int i=0;i<n;i++){
            sum+=diff[i];
        }
        return sum;
        
    }
};

吃掉N个橘子的最少天数

1553. 吃掉 N 个橘子的最少天数 - 力扣（LeetCode）

题目叙述：厨房里总共有 n 个橘子，你决定每一天选择如下方式之一吃这些橘子：

吃掉一个橘子。
如果剩余橘子数 n 能被 2 整除，那么你可以吃掉 n/2 个橘子。
如果剩余橘子数 n 能被 3 整除，那么你可以吃掉 2*(n/3) 个橘子。

每天你只能从以上 3 种方案中选择一种方案，请你返回吃掉所有 n 个橘子的最少天数。

思路：DP+贪心优化，如果n不能被2整除，则可以先吃n%2天(每天吃一个，吃到n%2==0),然后再用一天吃掉一半；如果n不能被3整除，则可以先吃n%3天(每天吃一个，吃到n%3==0)，然后用一天吃掉2*(n/3) 个。使用记忆化数组缓存状态。

代码：

class Solution {
public:
    //存吃完橘子数量所耗的天数
    unordered_map<int,int> dp;
    int minDays(int n) {
        if(n<=1) return 1;
        if(dp.find(n)!=dp.end()) return dp[n];
        //尽可能先吃到按比例吃的那一步
        int res=min(n%2+1+minDays(n/2),n%3+1+minDays(n/3));
        dp[n]=res;
        return res;
        
    }
};

课程表三

https://leetcode.cn/problems/course-schedule-iii/

题目叙述：有n门课程，对应course二维数组，每个元素对应二元组[课程持续时间，最晚截止时间]，课程必须不晚于最晚截止时间完成，你的学期从第一天开始并且不能同时修两门及以上的课程，求你可以修的最多科目数。

思路：贪心+堆。优先处理截止时间早的课程，按截止时间将课程排序，用大根堆记录已选课程的持续时间，对于没门课程，先尝试加入：若当前总时间+课程持续时间<=截止时间，说明可以加入，将课程加入堆并更新总时间；如果无法加入，则检查堆中是否有持续时间比当前课程更长的课程，如果有，替换这门时间最长的课程，因为替换后总时间会减少，可能腾出时间容纳更多课程），并更新总时间。

代码：

class Solution {
public:
    int scheduleCourse(vector<vector<int>>& courses) {
        //按截止日期从小到大排序
        sort(courses.begin(),courses.end(),[](const vector<int> &a,const vector<int> &b){
            return a[1]<b[1];
        });
        //大根堆(记录已选课程的持续时间)
        priority_queue<int,vector<int>,less<int>> heap;
        int time=0;//当前已用时间(已选课程的结束时间)
        for(auto course:courses){
            int a=course[0];//持续时间
            int b=course[1];//截止日期
            if(time+a<=b){
                heap.push(a);
                time+=a;
            } else if(!heap.empty() && heap.top()>a){
                //替换掉堆中维护的时间最长的课程
                time-=heap.top();
                heap.pop();
                heap.push(a);
                time+=a;
            }
        }
        return heap.size();
    }
};

最多可以参加的会议数目

1353. 最多可以参加的会议数目 - 力扣（LeetCode）

题目叙述：二维数组events表示会议数组，每个会议包含二元组[开始时间，结束时间]，可以在开始时间到结束时间的任意一天内参加该会议并且每天只能参加一场会议，返回能参加的最大会议数

思路：贪心＋堆优化。先将所有会议按开始时间从小到大排序，定义小根堆存会议的结束时间，堆顶是最早结束的会议，在同一天有多个可选会议时，选择最早结束的会议，能为后续会议腾出更多时间，从而参加更多会议。从所有会议的开始时间按天遍历到会议结束时间，对于每一天，先将当天开始的会议加入到堆，然后移除堆中已结束会议(结束日早于当天)，之后堆中若还有会议，选择结束最早的会议参加(堆顶)，同时从堆中移除会议。

代码：

class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        //按左端点排序
        sort(events.begin(),events.end(),[](const vector<int> &a,vector<int> &b){
            return a[0]<b[0];
        });
        //小根堆维护会议结束时间
        priority_queue<int,vector<int>,greater<int>> heap;
        //最晚截止时间
        int end=events[0][1];
        int start=events[0][0];
        for(int i=1;i<events.size();i++) end=max(end,events[i][1]);
        int index=0;//当前处理到的会议索引
        int res=0;
        for(int i=start;i<=end;i++){
            //将当前天的会议的结束时间入堆
            while(index<events.size() && events[index][0]==i){
                heap.push(events[index][1]);
                index++;
            }
            //移除过期会议
            while(!heap.empty() &&heap.top()<i){
                heap.pop();
            }
            //贪心选择堆中最早结束的会议
            if(!heap.empty()){
                heap.pop();
                res++;
            }
        }
        return res;
    }
};

IPO

502. IPO - 力扣（LeetCode）

题目叙述：n个项目，对于每个项目，对应一个纯利润profits[i]，和一个启动该项目所需的最小资本capital[i]，起初，你的资本为w，当你完成一个项目时，你将获得纯利润并将其添加到你的总资本中。从给定项目中选k个不同项目的列表，以最大化最终资本，输出最终可获得的最多资本。

思路：贪心＋双堆优化。对于每个项目，关键是在当前资本允许的范围内，优先选择利润最高的项目。小根堆1：存储未解锁的项目（按启动成本从小到大排序）；大根堆2：存储已解锁的项目(按利润从大到小排序)，每次迭代先解锁所有启动资本<=当前资本的项目(从堆1移到堆2)，从已解锁的项目堆2中选择利润最高的项目启动，并更新当前利润和k。

代码：

class Solution {
    //注：二元组中进行排序时，先按第一个属性进行排序，第一个相等再按第二个进行排序
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
        int n=profits.size();
        //小根堆存未解锁的项目（按启动成本从小到大排）[启动成本，利润]
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> heap1;
        //大根堆存已解锁的项目，按利润从大到小排 [利润，启动成本]
        priority_queue<pair<int,int>,vector<pair<int,int>>,less<pair<int,int>>> heap2;
    
        for(int i=0;i<n;i++){
            heap1.push({capital[i],profits[i]});
        }
        while(k>0){
            //解锁当前可启动的项目
            while(!heap1.empty() && heap1.top().first<=w){
                auto t=heap1.top();
                heap1.pop();
                heap2.push({t.second,t.first});
            }
            //没有可解锁的项目
            if(heap2.empty()) break;
            //选择已解锁的项目中利润最高的
            w+=heap2.top().first;
            heap2.pop();
            k--;
        }
        return w;
    }
};

最短无序连续子数组

581. 最短无序连续子数组 - 力扣（LeetCode）

题目叙述：给出整数数组nums，你需要找出一个子数组，使得将子数组升序排序后，整个数组都会升序排序，找出符合条件的最短子数组并输出子数组的长度。

思路：若该数组存在无序数组，那么在该子数组右侧必然存在元素小于其左侧的最大值；在子数组左侧必然存在元素大于其右侧的最小值。从左到右遍历数组，记录最大值，找到最后一个小于当前最大值元素的位置r；从右往左遍历数组，记录最小值，找到最后一个大于当前最小值的元素位置l,子数组长度：r-l+1。

代码：

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int r=-1; //区间右端点位置
        int max_v=-0x3f3f3f3f;
        for(int i=0;i<nums.size();i++){
            if(nums[i]<max_v){
                //当前被标记未不正确
                r=i;
            }
            max_v=max(max_v,nums[i]); 
        }
        int l=nums.size();
        int min_v=0x3f3f3f3f;
        for(int i=nums.size()-1;i>=0;i--){
            if(nums[i]>min_v){
                l=i;
            }
            min_v=min(min_v,nums[i]);
        }
        return max(0,r-l+1);
    }
};

最小区间

632. 最小区间 - 力扣（LeetCode）

问题叙述：有k个非递减排列的整数列表，找一个最小区间，使得k个列表中每个列表至少有一个数包含在其中。

思路：维护每个列表的一个“当前元素来构建候选区”，区间左边界由当前候选元素的最小值来决定，右边界由最大值决定，为了找到更小区间，我们应该尝试移动最小值所在列表的指针（因为增大最小值可能会缩小区间）。使用set来维护候选元素。

代码：

class Solution {
public:
    // 声明为public，确保外部可访问
    struct Node {
        int v; // 元素值
        int i; // 所在列表的索引
        int j; // 元素在列表中的位置
    };
    vector<int> smallestRange(vector<vector<int>>& nums) {
        int k = nums.size(); // 定义k为列表数量
        if (k == 0) return {}; // 边界条件：空输入
        // 自定义排序规则：先按值升序，值相同按列表索引升序
        auto cmp = [](const Node& a, const Node& b) {
            if (a.v != b.v) {
                return a.v < b.v;
            }
            return a.i < b.i;
        };
        // 有序集合，使用自定义比较器
        set<Node, decltype(cmp)> orderedSet(cmp);
        // 初始化：每个列表取第一个元素加入集合
        for (int i = 0; i < k; ++i) {
            orderedSet.insert({nums[i][0], i, 0});
        }
        int minLen = INT_MAX; // 最小区间长度，初始为极大值
        int l = 0, r = 0;     // 最小区间的左右边界
        // 当集合中包含所有k个列表的元素时，继续循环
        while (orderedSet.size() == k) {
            // 获取当前集合中的最大值（最后一个元素）和最小值（第一个元素）
            auto maxNode = *orderedSet.rbegin(); // 反向迭代器指向最大值
            auto minNode = *orderedSet.begin();  // 正向迭代器指向最小值
            // 计算当前区间长度，更新最小区间
            int curLen = maxNode.v - minNode.v;
            if (curLen < minLen) {
                minLen = curLen;
                l = minNode.v; // 修正：左边界是minNode的v
                r = maxNode.v;
            }
            // 弹出最小值节点，准备加入其所在列表的下一个元素
            orderedSet.erase(orderedSet.begin());
            int nextIndex = minNode.j + 1; // 下一个元素在列表中的位置
            // 若所在列表还有下一个元素，加入集合
            if (nextIndex < nums[minNode.i].size()) { // 修正：列表索引是minNode.i
                orderedSet.insert({
                    nums[minNode.i][nextIndex], // 下一个元素的值
                    minNode.i,                  // 所在列表的索引（不变）
                    nextIndex                   // 新的位置索引
                });
            }
        }
        return {l, r};
    }
};

数组最小偏移量

1675. 数组的最小偏移量 - 力扣（LeetCode）

题目描述：给定一个长度为n的数组nums，可以对数组中任意元素执行任意次数的两类操作，如果元素是偶数，可以将元素除以2，如果元素是奇数，可以将元素乘2。数组的偏移量是任意两个元素之间的最大差值，求数组执行某些操作后的最小偏移量。

思路：对于奇数，一直进行操作，则该数会在奇数和偶数之间震荡；对于偶数，一直操作，该数会先下降，下降到一定程度后再会进行奇数和偶数之间的震荡。我们先给所有奇数一次上升操作，此时，所有数均为偶数，我们用Set存所有偶数。之后我们开始迭代更新最小偏移量，只要Set中最大值是偶数，就将其执行除2操作并更新Set以缩小区间，同时不断更新最小偏移量。

代码：

class Solution {
public:
    //如果是偶数，一直操作，先下降，再震荡 【100，50，25，50，25，50】
    //如果是奇数，一直操作，会直接进入震荡 【25，50，25，50】
    //奇数只有一次上升机会，先给他这次机会，只讨论某个值下降时
    int minimumDeviation(vector<int>& nums) {
        set<int> s;
        for(int num:nums){
            if(num%2==0){
                s.insert(num);
            } else {
                s.insert(num*2);
            }
        }
        int res=*s.rbegin()-*s.begin();
        //直到最大值是奇数，无法再继续/2压缩，此时是差值最大的时候
        while(res>0 && *s.rbegin()%2==0){
            int max_v=*s.rbegin();
            s.erase(max_v);
            s.insert(max_v/2);
            res=min(res,*s.rbegin()-*s.begin());
        }
        return res;
    }
};

森林中的兔子

https://leetcode.cn/problems/rabbits-in-forest/description/

题目叙述：森林中有未知数量的兔子。提问其中若干只兔子 "还有多少只兔子与你（指被提问的兔子）颜色相同?" ，将答案收集到一个整数数组 answers 中，其中 answers[i] 是第 i 只兔子的回答。给你数组 answers ，返回森林中兔子的最少数量。

思路：将answers数组排序，尽可能地让回答相同数字的兔子属于同一种颜色。用双指针维护一个相同回答的区间，记录区间内兔子的数量，该颜色需要的兔子数量，累加结果。

代码：

class Solution {
public:
    int numRabbits(vector<int>& answers) {
        sort(answers.begin(),answers.end());
        int res=0;
        for(int i=0,j=1;i<answers.size();j++){
            int x=answers[i];
            while(j<answers.size() && answers[j]==x){
                j++;
            }
            //当前划分区域中兔子数量
            int cnt=j-i;
            //该颜色需要的兔子数量
            int groupSize=x+1;
            //累加数量(a/b上取整：(a+b-1)/b)
            res+=(cnt+groupSize-1)/groupSize*groupSize;
            i=j;
        }
        return res;
    }
};

使数组相似的最少操作次数

2449. 使数组相似的最少操作次数 - 力扣（LeetCode）

题目叙述：给出两个长度相同的数组nums，target。在一次操作中，你可以选择两个不同的下标i，j，令nums[i]=nums[i]+2且nums[j]=nums[j]-2。如果两个数组中每个元素出现频率相等，称两个数组是相似的。请返回nums变得与target相似的最少操作次数。

思路：首先，对每个数的操作是不改变奇偶性的，因此我们可以把两个数组的元素做奇偶分离并分别将每个数组的左右两部分进行排序，然后两个数组的每个元素再去做一一对应，记录每次操作前后元素的数值变化量(加2或减2)，每次操作影响4个变化量。

代码：

class Solution {
    //两种操作都不会改变元素的奇偶性
public:
    //将数组分割为左奇数右偶数，结果返回奇数部分的长度
    int split(vector<int> &arr){
        int cnt=0;
        for(int i=0;i<arr.size();i++){
            if(arr[i]%2==1){
                swap(arr[i],arr[cnt]);
                cnt++;
            }
        }
        return cnt;
    }
    long long makeSimilar(vector<int>& nums, vector<int>& target) {
        int odd=split(nums);
        split(target);
        sort(nums.begin(),nums.begin()+odd);
        sort(nums.begin()+odd,nums.end());
        sort(target.begin(),target.begin()+odd);
        sort(target.begin()+odd,target.end());
        long long res=0;
        for(int i=0;i<nums.size();i++){
            res+=(long long)abs(nums[i]-target[i]);
        }
        //每次操作可以平4个数
        return res/4;
    }
};

知识竞赛

知识竞赛_牛客题霸_牛客网

题目叙述：最近部门要选两个员工参与某竞赛，每个员工都对应一个推理能力Ai，阅读能力Bi，如果选择两个人去参加，则他们在推理能力表现出的能力为二人推理能力的平均值，阅读能力同样为二人阅读能力的平均值，现在想最大化他们较差一方面的能力，让Min(X,Y)尽可能大，问这个最大值是多少。

思路：首先按每个人的两种能力差值的绝对值对所有人能力进行排序，绝对值之差越小，这个人能力越均衡，这种人更容易让Min(X,Y)尽可能大。遍历每个员工，当员工推理能力较弱时，他的瓶颈在推理，让其与当前记录的有最大推理能力的人进行匹配，当员工阅读能力较弱时，他的瓶颈在阅读能力，让其与当前记录的有最大阅读能力的人进行匹配。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+50;
typedef pair<int,int> PII;
PII nums[N];
int n;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d%d",&nums[i].first,&nums[i].second);
    }
    //绝对值之差越小，这个人能力越均衡，这种人更容易让min(X,Y)更大
    sort(nums,nums+n,[](const PII &a,const PII &b){
        return abs(a.first-a.second)<abs(b.first-b.second);
    });
    //已经遍历的元素中最大推理能力和最大阅读能力
    int max_a=nums[0].first,max_b=nums[0].second;
    int res;
    for(int i=1;i<=n;i++){
        //当前员工推理能力较弱，瓶颈在推理，与已有的最大推理能力匹配
        if(nums[i].first<=nums[i].second){
            res=max(res,max_a+nums[i].first);
        } else {
            //当前员工阅读能力较弱，瓶颈在阅读能力
            res=max(res,max_b+nums[i].second);
        }
        max_a=max(max_a,nums[i].first);
        max_a=max(max_b,nums[i].second);
    }
    printf("%.1d",res/2);
    return 0;
}

最低加油次数

871. 最低加油次数 - 力扣（LeetCode）

题目叙述：汽车从起点出发驶向目的地，目的地位于出发东面位置target处。沿途有加油站，用数组stations表示，其中stations[i]=[position,fuel]表示第i个加油站位于出发位置东面position处，并且有fuel升汽油。假设汽车油箱无限，最初有startFuel升燃料，每行驶一英里就消耗一升燃料。当汽车到达加油站时，它可能停下来加油，将加油站所有汽油转到车上。为了到达目的地，求汽车所必须的最低加油次数。

思路：每到一个加油站，我们先不决定是否加油，而是将每个加油站的信息用大根堆缓存起来。我们开着车一直前进，当无法到达下一个加油站时，我们穿越回过去，回到油量最多的那个加油站进行加油(使得能尽量行驶地远)。注意处理最后一个加油站到终点地情况。

代码：

class Solution {
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        //初始油量足够到目的地
        if(startFuel>=target) return 0;
        //大根堆，存沿途经过加油站的油量
        priority_queue<int,vector<int>,less<int>> heap;
        //初始油量＋沿途加的油（能到达的位置）
        int to=startFuel;
        int cnt=0;
        for(vector<int> station:stations){
            int position=station[0];//位置
            int fuel=station[1];//油量
            //到不了这个位置了，穿越回某个位置进行加油
            if(to<position){
                while(!heap.empty() && to<position){
                    to+=heap.top();
                    heap.pop();
                    cnt++;
                    if(to>=target) return cnt;
                }
                //所有站全加油也无法到
                if(to<position) return -1;
            }
            heap.push(fuel);
        }
        //此时还没到终点
        while(!heap.empty()){
            to+=heap.top();
            heap.pop();
            cnt++;
            if(to>=target) return cnt;
        }
        //最终还是走不到终点
        return -1;
    }
};

灌溉花园的最少水龙头数目

1326. 灌溉花园的最少水龙头数目 - 力扣（LeetCode）

题目叙述：X轴上有一个长度为n的一维花园，花园共有n+1个水龙头。给出一个整数n和一个长度为n+1的整数数组ranges，其中ranges[i]表示：如果打开点i处的水龙头，可以灌溉区域为【i-rangesp[i],i+ranges[i]】,返回可以灌溉整个花园的最少水龙头数目。

思路：将问题转化为从左端点0开始，我们如何一步步跳到右端点n。对于点i,我们能跳到的最远距离取决于覆盖点i的水龙头中，覆盖范围最靠右端的一个，每次选择一个水龙头就相当于进行一次跳跃。定义right[i]数组存所有左边界能覆盖到点j的水龙头中，其能灌溉到的最远右边界。之后双指针迭代更新水龙头数量。在当前已覆盖的范围内 [0, cur]，不断寻找能跳到的最远点 next。走到当前覆盖范围的边界 cur 时，必须进行一次跳跃。跳跃到 next 的位置，更新覆盖范围 cur，并增加跳跃次数 res。如果在边界 cur 处无法再向前跳跃（next == cur），则说明无法覆盖，返回 -1.

代码：

class Solution {
public:
    int minTaps(int n, vector<int>& ranges) {
        //左边界为i的水龙头，能最远覆盖的右边界
        vector<int> right(n+1,0);
        for(int i=0;i<=n;i++){
            int left=max(0,i-ranges[i]);
            right[left]=max(right[left],i+ranges[i]);
        }
        int cur=0;//当前已经覆盖的右边界
        int next=0;//下一步能覆盖的右边界
        int res=0; //水龙头数量
        
        for(int i=0;i<n;i++){
            //更新下一次覆盖右边界
            next=max(next,right[i]);
            if(i==cur){ //能到达覆盖的右边界
                if(next>i){ //能延申覆盖范围
                    cur=next;
                    res++;
                } else {
                    return -1;
                }
            }
        }
        return res;
    }
};

超级洗衣机

517. 超级洗衣机 - 力扣（LeetCode）

题目叙述：有n台超级洗衣机放在同一排，开始的时候，每个洗衣机可能有一定量衣服，也可能是空的。每一步操作中，你可以选任意m台洗衣机，与此同时，你可以将每台洗衣机的一件衣服送到相邻的一台洗衣机。给定整数数组machines代表从左到右每台洗衣机中衣物数量，请给出能让所有洗衣机中剩下的衣物的数量相等的最小操作数。

思路：我们的目标是将每台机器的衣服数量调整到avg，对于任意一台洗衣机，它可能从左边接收衣服，也可能从右边接收衣服，或者需要向两边输出衣服。整个系统达到平衡需要的最小操作次数取决于最慢的环节。对于任意一台洗衣机：

左侧：计算本洗衣机左边机器共需要多少件衣服才能到达平衡以及它们现在有多少件衣服，这个差值，决定了必须穿过i和i-1之间边界的衣服数量。

右侧：同理，计算i右边所有机器的衣服需求，决定了必须穿过i和i+1之间边界的衣服数量。

对于洗衣机i本身，它可能也是一个瓶颈，如果它衣服太多，也需要把多余衣服送出去。

因此，整个系统的最少操作步数，就是所有位置中，这个瓶颈步数的最大值。

代码：

class Solution {
public:
    int findMinMoves(vector<int>& machines) {
        int n=machines.size();
        int sum=0;
        for(int i=0;i<machines.size();i++){
            sum+=machines[i];
        }
        if(sum%n!=0) return -1;
        int avg=sum/n;
        int leftSum=0;//左侧累加和
        int rightSum=0;//右侧累加和
        int leftNeed=0;//左边还需要多少件衣服
        int rightNeed=0;//右侧还需要多少件衣服
        int neck=0;//每一步的瓶颈
        int res=0;
        for(int i=0;i<n;i++){
             // 左侧需要的总衣服数 - 左侧已有的总衣服数 = 左侧还需要（或多余）的衣服数
            leftNeed=i*avg-leftSum;
            // 右侧需要的总衣服数 - 右侧已有的总衣服数 = 右侧还需要（或多余）的衣服数
            rightNeed=(n-i-1)*avg-(sum-leftSum-machines[i]);
            //左边缺衣服，右边也缺衣服
            if(leftNeed>0 && rightNeed>0){
                neck=leftNeed+rightNeed;
            } else {
                //至少有一边是衣服富余的
                neck=max(abs(leftNeed),abs(rightNeed));
            }
            leftSum+=machines[i];
            res=max(res,neck);
        }
        return res;
    }
};

过河问题

https://www.luogu.com.cn/problem/P1809

题目叙述：共N个人出游，他们走到一条河东岸边，想要过河到西岸。而东岸边有一条小船，船一次只能做两个人，每个人有一个渡河时间T，船划到对岸的时间等于船上渡河时间较长的人所用的时间。现已知N个人的渡河时间T，求所有人渡河要花费的最小时间。

思路：两种最省时间的方案，一是让最小耗时的人往复载其他人过去，另一种是先让最小耗时的两个人开过去，然后回来一个运人。使用DP递推

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+50;
int n;
int arr[N];
int dp[N];//0-i号人过河的代价
//两种最省时间的方案：
//让最小耗时的船往复待其他船过去，让其往复往回开船运人
//先让最小耗时的两个船过去，然后回来一个运人
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>arr[i]; 
    sort(arr,arr+n);
    dp[0]=arr[0];
    dp[1]=arr[1];
    dp[2]=arr[0]+arr[2]+arr[1];//a,c先过去，a把船开回来，然后把b带过去
    for(int i=3;i<n;i++){
        //0号人把船开回来并把最后一个人拉过去
        //把最后两人绑定,0或1开船回来一个,i和i-1开船回去,之后0/1中的另一个开船过来，01一起回对岸
        dp[i]=min(dp[i-1]+arr[i]+arr[0],dp[i-2]+arr[1]+arr[i]+arr[1]+arr[0]);
    }
    cout<<dp[n-1]<<endl;
    return 0;
}

消灭怪物的最大数量

1921. 消灭怪物的最大数量 - 力扣（LeetCode）

题目叙述：给定数组dist表示每个怪物与城市的初始距离，怪物以恒定速度向城市进攻，每个怪物对应一个speed。你有一种武器，一旦充满电，就可以消灭一个怪物，但是武器需要一分钟才能充满电，武器初始时是满电状态，怪物从第0分钟开始移动，一点怪物到达城市，你就失败。求输掉游戏前你能消灭的最大怪物数量。

思路：我们用time数组记录每个怪物到达城市的时间，按时间到达顺序进行排序，看那个怪物可以在充好电之前就进攻城市。

代码：

class Solution {
public:
    int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
        vector<int> time(dist.size(),0);
        for(int i=0;i<dist.size();i++){
            //上取整 （a+b-1）/b
            time[i]=(dist[i]+speed[i]-1)/speed[i];
        }
        sort(time.begin(),time.end());
        for(int i=0;i<time.size();i++){
            if(i>=time[i]) return i;
        }
        return time.size();
    }
};

最大回文数字

2384. 最大回文数字 - 力扣（LeetCode）

题目叙述：给一个仅有数字0-9组成的字符串num，找出能够使用num中数字形成的最大回文整数，并以字符串返回，该整数不含前导0。

思路：一个回文数具有对称性，我们构建一个回文数，可以先构建左半部分(左半部分越大，回文数越大)。贪心策略体现在优先使用大的数字，将大数字进可能放到高位，对于每个数字d，最多使用count[d]/2对d来构建左右两部分。定义cnt数组统计每个数的出现频率。首先构建回文数的左半部分，从大到小选数，如果当前数的频率为奇数且没有选出中心点，则将其选为中心点。左右迭代构建回文串。

代码：

class Solution {
public:
    string largestPalindromic(string num) {
        //统计数字出现次数
        int n=num.size();
        vector<int> cnt(128,0);
        for(char c:num){
            cnt[c]++;
        }
        string res;
        char mid=0;//中心字符（长度为奇数时）
        //构建回文串左半部分（不包括中点）从大字符开始处理
        for(char c='9';c>='1';c--){
            //当前字符有奇数个，并且还没有选出中心点
            if((cnt[c]&1) && mid==0){
                mid=c;
            }
            //取出当前字符的一半数量加入左部分
            int half=cnt[c]/2;
            for(int i=0;i<half;i++){
                res.push_back(c);
            }
        }
        //特殊情况，左半部分为空
        if(res.empty()){
            if(mid==0) return "0";
            else return string(1,mid);
        }
        //处理0字符，此时左边已有非0字符，补充到左半部分
        int zeroHalf=cnt['0']/2;
        for(int i=0;i<zeroHalf;i++){
            res.push_back('0');
        }
        //记录左半部分长度，用于构建右半部分
        int leftSize=res.size();
        //处理中点字符，若还没有选中心，看0能不能做中心
        if(mid==0 && (cnt['0']&1)){
            mid='0';
        }
        //若有中心字符，加入结果
        if(mid!=0){
            res.push_back(mid);
        }
        //构建右半部分
        for(int i=leftSize-1;i>=0;i--){
            res.push_back(res[i]);
        }
        
        return res;
    
    }
};

最大平均通过率

1792. 最大平均通过率 - 力扣（LeetCode）

题目叙述：给出二维数组classes，classes[pass,total]表示该班级里有total个学生，其中只有pass个学生可以通过考试。给出整数extraStudents,表示额外的聪明学生数量，他们一定会通过考试。现在我们将这extraStudents个学生没人都安排一个班级，使得所有班级的平均通过率最大。返回分配完成后所有班级整体的最大平均通过率。

思路：定义大顶堆存每个班级加一个天才后通过率的提升值。优先给提升值大的班级分配天才，分配完毕后计算整体通过率。

代码：

class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        int n=classes.size();
        //大顶堆，存每个班加一个天才后的通过率提升值
        //堆的排序依据是第一个元素
        priority_queue<
            pair<double, pair<double, double>>,  // 元素类型
            vector<pair<double, pair<double, double>>>,  // 底层容器（修正：补全右尖括号）
            less<pair<double, pair<double, double>>>  // 比较器（大顶堆）
        > heap;  // 堆对象
        for(vector<int> c:classes){
            double a=c[0];
            double b=c[1];
            double inc=(a+1)/(b+1)-a/b;
            heap.push({inc,{a,b}});
        }
        //分配天才学生
        while(extraStudents-->0){
            auto top=heap.top();
            heap.pop();
            double inc=top.first;
            double a=top.second.first;
            double b=top.second.second;
            a++;
            b++;
            double newInc=(a+1)/(b+1)-a/b;
            heap.push({newInc,{a,b}});
        }
        //计算平均通过率
        double total=0;
        while(!heap.empty()){
            auto cur=heap.top();
            heap.pop();
            total+=cur.second.first/cur.second.second;
        }
        return total/n;
    }
};

算法学习笔记-贪心算法总结2

最大数

两地调度

吃掉N个橘子的最少天数

课程表三

最多可以参加的会议数目

IPO

最短无序连续子数组

最小区间

数组最小偏移量

森林中的兔子

使数组相似的最少操作次数

知识竞赛

最低加油次数

灌溉花园的最少水龙头数目

超级洗衣机

过河问题

消灭怪物的最大数量

最大回文数字

最大平均通过率

热门文章

最新文章

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

算法学习笔记-贪心算法总结2

最大数

两地调度

吃掉N个橘子的最少天数

课程表三

最多可以参加的会议数目

IPO

最短无序连续子数组

最小区间

数组最小偏移量

森林中的兔子

使数组相似的最少操作次数

知识竞赛

最低加油次数

灌溉花园的最少水龙头数目

超级洗衣机

过河问题

消灭怪物的最大数量

最大回文数字

最大平均通过率

热门文章

最新文章

相关电子书