放牧代码和思想
专注自然语言处理、机器学习算法
    时间有限,只有GitHub上的issue能及时处理,大约每周末一次。另外,不要叫我楼主,谢谢。

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版)》

分享到:更多 ()

评论 1

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    其实不用最小堆的,目前两个最大的元素合体之后必然仍是最大的

    karia2年前 (2016-01-12)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机