火柴拼图题解

对于同一种长度L的火柴，3根我们会构成正三角形；4-5根会构成正四边形。那么对于6根呢？6根可以拆成两个正三角形或者一个正四边形。我们发现两个正三角形的面积和为,而一个正四边形的面积是，所以毫无疑问我们会选择拆为正四边形。就相当于是能拆正四边形我就拆正四边形，不行我就拆正三角形。随后我们只需要统计每一种长度的出现个数，再计算一次答案即可。时间复杂度O(n)，空间复杂度O(n)。

class Solution {
public:
    vector<long> MaxArea(int n, vector<int>& Stick) {
        // write code here
        long long a=0,b=0;
        vector<int>cnt;
        cnt.resize(100001);
        for(auto i:Stick) cnt[i]++;
        for(int i=1;i<=100000;i++) {
            b+=1ll*(cnt[i]/4)*i*i;
            if(cnt[i]%4==3)
                a+=1ll*i*i;
        }
        return {a,b};
    }
};