POJ 1862 Stripies 题解 《挑战程序设计竞赛(第2版)》

2.2 一往直前！贪心法 其他

POJ 1862 Stripies

变形虫：从N个数任取两个数按2*sqrt(a*b)合成新数放回，求最后那个数的最小值。

贪心策略是使尽量使大的数多参与开放运算。每次取出最大和次大的变形虫杂交，直至剩下一条光棍。使用最大堆可以很高效地维持最大的数。

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
	int N;
	cin >> N;
	priority_queue<double> que;
	for (int i = 0; i < N; ++i)
	{
		double l;
		cin >> l;
		que.push(l);
	}
	while(que.size() != 1)
	{
		double a = que.top(); que.pop();
		double b = que.top(); que.pop();
		que.push(2 * sqrt(a * b));
	}
	cout.setf(ios::fixed);
	cout.precision(3);
	cout << que.top() << endl;
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("out.txt");
#endif
    return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 1862 Stripies 题解 《挑战程序设计竞赛(第2版)》