【POJ - 1862】Stripies （贪心）

sky-stars 2019-08-05 原文

【POJ – 1862】Stripies （贪心）

Stripies

直接上中文了

Descriptions

我们的化学生物学家发明了一种新的叫stripies非常神奇的生命。该stripies是透明的无定形变形虫似的生物，生活在果冻状的营养培养基平板菌落。大部分的时间stripies在移动。当他们两个碰撞，会有新stripie生成，而旧的不见了。经过长期研究，他们发现新stripies的体重不等于消失的stripies的体重，而是：如果一个质量为m1和m2的stripies相撞，生成的stripies体重是2*sqrt(m1*m2) 现在，科学家们想知道，如果stripies两两碰撞至只剩一个，则这一个的最小质量是多少？

Input

第一行输入 N (1 <= N <= 100) ：stripies的数量. 接下来的 N 行是stripies的质量（1<=m<=10000）

Output

输出最小质量。保留至小数点后三位

Sample Input

Sample Output

120.000

Hint

样例解释：
72与50合并，产生120,120与30合并，产生120

题目链接

https://vjudge.net/problem/POJ-1862

贪心算法，2*sqrt(m1*m2) 有这个式子易得m1和m2应该每次都是这个数组里最大的两个数，想到这就简单了，每次排个序就行了

AC代码

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define Mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
#define Maxn 100000+100
using namespace std;
int n;
double m[Maxn];
bool cmp(double x,double y)//m数组按从大到小排序
{
    return x>y;
}
double fun(double m1,double m2)//题目要求的函数
{
    return 2*sqrt(m1*m2);
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>m[i];
    sort(m,m+n,cmp);//排序
    while(m[1]!=0)
    {
        m[0]=fun(m[0],m[1]);//更新
        m[1]=0;
        sort(m,m+n,cmp);
//        不懂的看一加上下面的注释看一下里面的操作
//        for(int i=0;i<n;i++)
//            cout<<m[i]<<" ";
//        cout<<endl;
    }
    printf("%.3f\n",m[0]);
    return 0;
}