9 POJ 1862 Stripies 简单贪心

前端之家收集整理的这篇文章主要介绍了9 POJ 1862 Stripies 简单贪心前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

视察发现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; }


猜你在找的PHP相关文章