首页 > 代码库 > 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 }
A----奇怪的玩意
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。