题解 P1284 【三角形牧场】

· · 题解

阅读这篇题解，你将会了解到如何优雅地使用随机化贪心完成此类题目以及贪心原则的证明。

首先，通过观察题目，我们发现数据量很小，甚至枚举都能拿高分，那么我们考虑比枚举更加灵活的随机化。

第二，我们可以确定：当满足三角形存在的情况下，选择的边越多越好。又有：我们的目标是最大化三角形面积，则可以如此思考：

在周长固定（所选边相同）的情况下，设边长为a,b,c。则面积可由秦九韶公式（国产海伦）得到为：S=\sqrt{p*(p-a)*(p-b)*(p-c)}

那么p是定值（周长一半），我们把右边根号下的东西打开，就是：一个含有a,b,c三个变量的表达式，由柯西不等式或是三阶均值不等式性质可以得到：当a,b,c越接近时，有该表达式最大，即面积最大。

有了这个结论，那我们就可以如此操作：每次随机化确定要选的边的顺序（顺序改变可能导致三角形木板数量的变化，因为可能会提前达到无法加边的时刻）

然后取三角形三边，每次给最小边发福利加上新边长度，就有点像谁短补谁的模式，如此一来就能保证三边长最为接近。

插一句题外话：具体为什么谁短补谁上面这个方法也可以应用于成绩，每次补最差的学科，这样可以保证各科均衡。（感性理解下吧）

步骤已经结束了，我们来想想如何优雅的实现：使用STL。

那么一个完美的随机化程序出炉了：

#include <bits/stdc++.h>
#define ri register int
#define ll long long
#define db double
using namespace std;
int read()
{
    int num=0;
    int flg=1;
    char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
        {
            flg=-1;
        }
        c=getchar();
    }
    while(isdigit(c))
    {
        num=(num<<1)+(num<<3)+(c^48);
        c=getchar();
    }
    return num*flg;
}

int calc(db one,db two,db three)
{
    if((one+two>three)&&(one+three>two)&&(two+three>one))
    {
        db p=(one+two+three)/2;
        return trunc(sqrt(p*(p-one)*(p-two)*(p-three))*100);
    }//要的是面积的100倍
    else
    {
        return -20031125;
    }
}//秦九韶

const int maxn=45;
int n;
int l[maxn];
priority_queue<int,vector<int>,greater<int> >q;//小根堆

int main()
{
    int ans=-1;
    n=read();
    for(ri i=1; i<=n; i++)
    {
        l[i]=read();
    }
    for(ri i=1; i<=10000; i++)
    {
        random_shuffle(l+1,l+n+1);//随机重排
        for(ri j=1; j<=3; j++)
        {
            q.push(l[j]);
        }
        for(ri j=4; j<=n; j++)
        {
            int top=q.top();
            q.pop();
            top+=l[j];
            q.push(top);
        }//每次给最短边加长
        int one=q.top();
        q.pop();
        int two=q.top();
        q.pop();
        int three=q.top();
        q.pop();
        ans=max(ans,calc(one,two,three));//更新答案
    }
    return 0&printf("%d",ans);
}

好！那题解到此就结束了，我想在此提几条Tips：

感谢您的耐心观看，您的支持是我继续写题解的动力！