数据结构与算法：贪心（一）

前言

有一说一贪心的题目真的ex，想不到就是想不到……

一、贪心

贪心就是通过在过程中每次达到局部最优，从而在最后实现整体最优。贪心的题目经常要用到排序和堆。

越打cf越能感受到贪心的奇妙，很吃状态和灵感。解题的过程中往往依赖举大量例子，然后进行总结和归纳，然后才能发现规律。当然不排除怎么举都想不到的情况，此处点名上次edu的b题斐波那契叠正方形。

二、题目

1.最大数

class Solution {
public://经典问题：组成字典序最小的字符串 -> 重新定义比较规则：a+b<b+a，比较拼接后结果string largestNumber(vector<int>& nums) {//转字符串vector<string>arr(nums.size());for(int i=0;i<nums.size();i++){arr[i]=to_string(nums[i]);}//最大字典序sort(arr.begin(),arr.end(),[&](const string &a,const string &b){return a+b>b+a;});//特判if(arr[0]=="0"){return "0";}string ans;for(string s:arr){ans+=s;}return ans;}
};

这个题我记得上学期在洛谷就刷到过一道类似的，当时第一次写，然后很幸运地踩坑里了……T^T

多举几个例子观察一下就能发现，不管是从小到大排序还是从大到小排序，都无法保证拼出来的字符串字典序最大，所以就要考虑重新定义比较规则。这里的方法是，比较两个字符串a和b，以a+b和b+a这两种拼接方式拼接后的字典序大小。若a+b的字典序更大，就让a排在b前。

这个初见真的想不到……

2.两地调度

class Solution {
public:int twoCitySchedCost(vector<vector<int>>& costs) {int n=costs.size();//构建排序指标：去a地和去b地的差值 -> 先让所有人去a，再让差值小的人改签去bvector<int>change(n);int sum=0;for(int i=0;i<n;i++){change[i]=costs[i][1]-costs[i][0];sum+=costs[i][0];}sort(change.begin(),change.end());int m=n/2;for(int i=0;i<m;i++){sum+=change[i];}return sum;}
};

这个题的关键还是对排序策略的定义。

思路是，先让所有人都去a，然后考察每个人从a转去b的代价，让代价最小的n个人去b。所以就是根据每个人去b的代价减去去a的代价从小到大排序，最后再把前n个人的这个代价加上即可。

3.吃掉 N 个橘子的最少天数

class Solution {
public:int minDays(int n) {map<int,int>dp;return dfs(n,dp);}//记忆化搜索int dfs(int n,map<int,int>&dp){if(n==0){return 0;}if(n==1){return 1;}if(dp[n]!=0){return dp[n];}//贪心策略：大于1的话必然选择按比例吃！！int ans=min(n%2+1+dfs(n/2,dp),n%3+1+dfs(n/3,dp));dp[n]=ans;return ans;}
};

这个题的贪心策略就是，当剩余数量大于1的时候必然选择按比例吃。此时，可能要先根据余数吃到能按比例吃的状态。所以在记忆化搜素的过程中，就是先把当前数量除以2或3的余数吃了，再按比例吃一次，之后去后续调递归，取最小值即可。

4.会议室

虽然这是个付费题，但转化一下就能发现，这就是之前线段重合的问题，一模一样。这里直接就放线段重合的代码了。

#include <bits/stdc++.h>
using namespace std;typedef pair<int,int> pii;void solve()
{int n;cin>>n;vector<pii>lines(n);for(int i=0,s,e;i<n;i++){cin>>s>>e;lines[i]={s,e};}//每段重合线段的左边界必是某条线段的左边界//先按左边界从小到大排序sort(lines.begin(),lines.end(),[&](const pii &a,const pii &b){return a.first<b.first;});priority_queue<int,vector<int>,greater<int>>heap;//小根堆int ans=0;for(int i=0;i<