C++, python貪婪演算解多邊形問題Leetcode 2971 Find Polygon With the Largest Perimeter

C++, python貪婪演算解多邊形問題Leetcode 2971  Find Polygon With the Largest Perimeter

程式實作不難，用貪婪演算即可，有人知其然不知所以然，貪婪演算是否可用是需要數學證明的，下面有一個用make_heap的解答，保留在此

----

It is not difficult to implement the program, just use greedy algorithm. Some people know it but don’t know why. Whether greedy algorithm can be used needs mathematical proof.

[codes on Leetcode]https://leetcode.com/problems/find-polygon-with-the-largest-perimeter/solutions/4728959/sort-prefix-sum-why-greedy-works-33ms-beats-100/

[Leetcode playList]https://www.youtube.com/watch?v=WjrWkPysfRM&list=PLYRlUBnWnd5IdDHk2BjqXwesydU17z_xk

[Dynamic Programming Playlist]https://www.youtube.com/watch?v=30yq3fmE6E8&list=PLYRlUBnWnd5K_XYUesV9oc6M9ONXII61T

#pragma GCC optimize("O3", "unroll-loops")
class Solution {
public:
    static long long largestPerimeter(vector<int>& nums) {
        int n=nums.size();
        long long perimeter=accumulate(nums.begin(), nums.end(), 0LL);
        make_heap(nums.begin(), nums.end());
        for(int i=n-1; i>=2; i--){
            pop_heap(nums.begin(), nums.end());
            int largest=nums.back();
            nums.pop_back();
            if (largest<perimeter-largest) return perimeter;
            perimeter-=largest;
        }
        return -1;
    }
};
 
 
auto init = []()
{ 
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 'c';
}();