贪心算法详解：从局部最优到全局最优

LeetCode 2208. 将数组和减半的最少操作次数

题目要求最小次数地对数组里的数除以 2，使数组和小于等于原先数组的一半。直觉上，每次找数组里面最大的数，然后给它减去一半是最优策略。

这里使用 priority_queue（默认大堆）可以很快解决问题。每插入一个数都会自动排序，我们只要不断取出堆顶元素进行处理即可。

class Solution {
public:
    int halveArray(vector<int>& nums) {
        priority_queue<double> p;
        double originalSum = 0;
        double currentSum = 0;
        for(auto& a : nums) {
            originalSum += a;
            currentSum += a;
            p.push(a);
        }
        originalSum /= 2;
        int mem = 0;
        while(currentSum > originalSum) {
            double tmp = p.top() / 2;
            p.pop();
            currentSum -= tmp;
            p.push(tmp);
            mem++;
        }
        return mem;
    }
};

LeetCode 179. 最大数

题目的意思是用数组里面的数组成一个最大的数。关键在于组合后数字的大小来决定排序顺序。

既然通过组合后数字的大小来排序，我们可以直接重写 sort 的排序规则。通过 lambda 表达式比较拼接后的字符串大小，就能得出结果。

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        vector<string> str;
        for(auto& s : nums) str.push_back(to_string(s));
        sort(str.begin(), str.end(), [](const string& s1, const string& s2){
            return s1 + s2 > s2 + s1;
        });
        string tmp;
        for(auto& s : str) tmp += s;
        if(tmp[0] == '0') return "0";
        else return tmp;
    }
};