程序员人生 网站导航

9 POJ 1862 Stripies 简单贪心

栏目:php教程时间:2015-06-24 08:26:55

视察发现m1+m2变成2*sqrt(m1*m2)质量是能够减少的,

因此按质量从大到小排序,每次取最大质量的两个合并,减少的质量是最多的。

合并n⑴次,终究得到的1个数就是结果。

这里用优先队列写的比较方便。


#include<cstdio> #include<queue> #include<cmath> using namespace std; priority_queue<double> q; int main() { int n,i; double x,a,b; while(~scanf("%d",&n)) { while(!q.empty()) q.pop(); for(i=0;i<n;i++) { scanf("%lf",&x); q.push(x); } for(i=0;i<n⑴;i++) { a=q.top();q.pop(); b=q.top();q.pop(); q.push(2*sqrt(a*b)); } printf("%.3lf ",q.top()); } return 0; }


------分隔线----------------------------
------分隔线----------------------------

最新技术推荐