首页 > 代码库 > 洛谷 P1284 三角形牧场WD
洛谷 P1284 三角形牧场WD
P1284 三角形牧场
题目描述
和所有人一样,奶牛喜欢变化。它们正在设想新造型的牧场。奶牛建筑师Hei想建造围有漂亮白色栅栏的三角形牧场。她拥有N(3≤N≤40)块木板,每块的长度Li(1≤Li≤40)都是整数,她想用所有的木板围成一个三角形使得牧场面积最大。
请帮助Hei小姐构造这样的牧场,并计算出这个最大牧场的面积。
输入输出格式
输入格式:
第1行:一个整数N
第2..N+1行:每行包含一个整数,即是木板长度。
输出格式:
仅一个整数:最大牧场面积乘以100然后舍尾的结果。如果无法构建,输出-1。
输入输出样例
输入样例#1:
5 1 1 3 3 4
输出样例#1:
692
说明
样例解释:692=舍尾后的(100×三角形面积),此三角形为等边三角形,边长为4。
#include <iostream> #include <cstdio> #include <cmath> #include <cstdlib> using namespace std; int n,a[41],ans=-1; void wash()//随机洗木板顺序 { for(int i=1;i<=n;i++) { int t=rand()%n; a[0]=a[t]; a[t]=a[i]; a[i]=a[0]; } } int hl(double aa,double bb,double cc)//海伦公式求面积 { if(aa+bb>cc&&bb+cc>aa&&aa+cc>bb) { double p=(aa+bb+cc)/2; return trunc(sqrt(p*(p-aa)*(p-bb)*(p-cc))*100); } else return -1; } void work()//贪心程序 { int p[3],pos; p[0]=a[1];p[1]=a[2];p[2]=a[3]; for(int i=4;i<=n;i++) { int min=0x7fffffff; for(int j=0;j<=2;j++) { if(min>p[j]) { min=p[j]; pos=j; } } p[pos]+=a[i]; } ans=max(ans,hl(p[0],p[1],p[2])); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=10000;i++) { wash(); work(); } printf("%d\n",ans); return 0; }
洛谷 P1284 三角形牧场WD
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。