poj 1862 Stripies 贪心

缘起

日常浪费生命 poj 1862 Stripies

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
两个物体m1、m2相撞后会变成一个物体，这个物体的重量会变成2*sqrt(m1*m2)。有n个物体，假设只会发生两两相
撞，求最后剩下的最小重量

【输入】
首先是一行为物体的数量N, 然后N行分别是这些物品的数量

【输出】
最小的重量, 精确到小数点后三位

【样例输入】
3
72
30
50

【样例输出】
120.000

注意基本的数学不等式

m1+m2>=2*sqrt(m1*m2)

而且左边-右边=(sqrt(m1)-sqrt(m2))^2

所以m1和m2差距越大, 缩水的重量就越大. 所以每次挑两个重量最大的物体杂交, 直至最后剩下一条光棍. 而求最大这一点可以使用堆进行高效的维护.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//#include "stdafx.h"

#include <stdio.h>
#include <iostream>
#include <queue>
#include <math.h>
#include <iomanip>
using namespace std;
//#define LOCAL

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	priority_queue<double, vector<double>, less<double> > pq; // 大根堆
	int n;
	scanf("%d", &n);
	while(n--)
	{
		int t;
		scanf("%d", &t);
		pq.push(t);
	}
	double ans;
	while(pq.size()>1)
	{
		double _1 = pq.top();
		pq.pop();
		double _2 = pq.top();
		pq.pop();
		pq.push(2*sqrt(_1*_2));
	}
	cout << fixed << setprecision(3) << pq.top();
	return 0;
}

ac情况

Status Accepted
Memory 156kB
Length 611
Lang C++
Submitted 2019-08-26 07:18:22
Shared
RemoteRunId 20801159