首页 > 代码库 > A----奇怪的玩意

A----奇怪的玩意

 
题目:
我们的化学生物学家发明了一种新的叫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

3
72
30
50

Sample Output

120.000

解题思路:
显然这一题需要用优先队列来储存每个小虫以及碰撞后的的质量。
要想得到最小的质量,就要注意他们碰撞后计算质量的公式:M=2*sqrt(m1*m2).我们要知道sqrt(m*m1)的值肯定位于m与m1之间,把所有的质量从小到大排序m1,m2,m3...;
如果从小的一头开始碰撞,则碰撞后的质量ans=sqrt(m1*m2)肯定大于m1,再碰撞sqrt(ans*m3)的结果肯定大于ans。不难发现,每一次碰撞后ans都在往右边移动(也就是大的一边)显然与题意相反;
因此,必须从大的一端开始碰撞,则碰撞后ans的质量都在往左移动(小的一边),所以得到最后的质量是最小的。
技术分享
 1 #include <iostream>
 2 #include <queue>
 3 #include <cmath>
 4 #include <cstdio>
 5 using namespace std;
 6 
 7 int main()
 8 {
 9     int i,n;
10     float ans,x1,x2,k;
11     priority_queue<float,vector<float> >pq;
12     cin >>n;
13     for (i=0;i<n;i++)
14     {
15         cin >>k;
16         pq.push(k);
17     }
18     while (pq.size()!=1)
19     {
20         x1=pq.top();pq.pop();
21         x2=pq.top();pq.pop();
22         ans=2*sqrt(x1*x2);
23         pq.push(ans);
24     }
25         printf("%0.3f",pq.top());
26     return 0;
27 }
AC代码

 






A----奇怪的玩意