前言

有一說一貪心的題目真的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<