题意

有n根火柴，可以用其中长度相同的火柴拼成正方形或正三角形，求能拼成的最大面积。

100分做法：暴力枚举

对于每一种不同长度的火柴，枚举组成正方形和三角形的个数，并计算最大面积。

class Solution {
public:
    
    void calc(int l,int t,vector<long> &ans)
    {
        int Sqa=0;
        int Tri=0;
        const double a=sqrt(3)/4;
        double maxx=0.0;
        int maxSqa=0;
        int maxTri=0;//存贮组成最大面积时的三角形和正方形个数
        for(Sqa=0;Sqa<=t/4;Sqa++) {
          Tri=(t-4*Sqa)/3;
          double tmp=a*Tri+Sqa;
          if(tmp>maxx)
          {
            maxx=tmp;
            maxSqa=Sqa;
            maxTri=Tri;
           }
        }
        ans[1]+=(maxSqa*l*l);
        ans[0]+=(maxTri*l*l);//存储答案
    }
    vector<long> MaxArea(int n, vector<int>& Stick)
    {
        vector<long> ans(2,0);//答案数组
        vector<int> stick(100005,0);//stick[Len]=Num表示长度为Len的火柴有Num根
        sort(Stick.begin(),Stick.end());
        for(int i=0;i<n;i++) stick[Stick[i]]++;//预处理stick
        for(int i=0;i<=Stick[n-1];i++) 
            calc(i,stick[i],ans);//对于每一种火柴，计算其能组成的最大面积
            return ans; 
    }
};

时间复杂度：$O(n\ast maxStickLength+nlogn)O(n*maxStickLength+nlogn)$O(n∗maxStickLength+nlogn),其中$maxStickLengthmaxStickLength$maxStickLength是最长木棍的长度，对于不同的长度，需要执行n/4次计算，与排序的时间相加就是时间复杂度。

空间复杂度：$O\left(n\right)O(n)$O(n)，过程中使用的$stickstick$stick数组占用的空间为$O\left(n\right)O(n)$O(n)。

100分做法：贪心

贪心思路，有火柴时先组成正方形，剩下的火柴组成正三角形，这个贪心的证明是显然的，过程如下。 故有6根火柴时组成一个正方形比两个三角形更好，因此我们的贪心策略是正确的。（图片只为直观展示三角形面积和正方形面积关系。）

class Solution {
public:
    
    void calc(int l,int t,vector<long> &ans)
    {
        int Sqa=t/4;//根据贪心，尽量要多组成正方形
        int Tri=(t%4==3)?1:0;//如果还有多余的三根木棍可以组成三角形
        ans[1]+=(Sqa*l*l);
        ans[0]+=(Tri*l*l);
    }
    vector<long> MaxArea(int n, vector<int>& Stick)
    {
        vector<long> ans(2,0);//答案数组
        vector<int> stick(100005,0);//stick[Len]=Num表示长度为Len的火柴有Num根
        sort(Stick.begin(),Stick.end());
        for(int i=0;i<n;i++) stick[Stick[i]]++;//预处理stick
        for(int i=0;i<=Stick[n-1];i++) 
            calc(i,stick[i],ans);//对于每一种火柴，计算其能组成的最大面积
            return ans; 
    }
};

时间复杂度：$O(maxStickLength+nlogn)O(maxStickLength+nlogn)$O(maxStickLength+nlogn),其中$maxStickLengthmaxStickLength$maxStickLength是最长木棍的长度，运用贪心，每个长度只需要常数基本时间，再与排序所用的时间相加。

空间复杂度：$O\left(n\right)O(n)$O(n)，过程中使用的$stickstick$stick数组占用的空间为$O\left(n\right)O(n)$O(n)。