题意略.
思路: 再思考后发现, 为了构造出最大的三角形面积和, 我们应该尽量让长的棍子相组合, 这样构造出的三角形面积和最大, 贪心能解.
- #include<bits/stdc++.h>
- using namespace std;
- double store[15];
- int n;
- double cal(double a,double b,double c){
- double p = (a + b + c) / 2;
- return sqrt(p * (p - a) * (p - b) * (p - c));
- }
- bool judge(double a,double b,double c){
- return (fabs(a - b) <c && c < a + b);
- }
- int main(){
- while(scanf("%d",&n) == 1 && n){
- for(int i = 0;i < n;++i){
- scanf("%lf",&store[i]);
- }
- sort(store,store + n);
- double ans = 0;
- for(int i = n - 1;i>= 2;){
- double a = store[i],b = store[i - 1],
- c = store[i - 2];
- if(judge(a,b,c)){
- ans += cal(a,b,c);
- i -= 3;
- }
- else{
- --i;
- }
- }
- printf("%.2lf\n",ans);
- }
- return 0;
- }
- HDU 5135(再思考)
来源: http://www.bubuko.com/infodetail-2639575.html