1 条题解
-
0
这段代码解决的是 Stripies 问题,其核心原理是通过贪心策略最小化生物融合后的总重量。
算法原理
问题分析:每次将两个生物融合为一个新生物,新生物的重量为
2*sqrt(a*b)
,目标是使最终剩下的生物重量最小。贪心策略:每次选择当前最重的两个生物进行融合。
数学原理:对于非负实数a ≥ b ≥ c ≥ d
,有2*sqrt(a*b) ≥ 2*sqrt(c*d)
。
反复应用此策略,可使每次融合后的新重量尽可能小,从而最终结果最小。数据结构:使用最大堆(优先队列)维护当前最重的生物,每次取出堆顶的两个元素进行融合,并将结果放回堆中。
关键步骤
初始化:将所有生物的重量放入最大堆。 循环融合:每次取出堆顶两个元素,计算新重量
2*sqrt(a*b)
,放回堆中,直到堆中只剩一个元素。 输出结果:堆中最后一个元素即为最小可能的最终重量。#include <cstdio> #include <cstring> #include <stack> #include <queue> #include <algorithm> #include<iostream> #include<map> #include<set> #include<math.h> using namespace std; #define MAX_A 10000 int cmp(int a,int b){ return a<b; } //维护一个优先队列 priority_queue <double> pque; int main(){ int n; scanf("%d",&n); double j; for(int i=0;i<n;i++){ scanf("%lf",&j); pque.push(j); } int k = n;//当前stripiesd的数量 while(k!=1){ double a,b; a = pque.top(); pque.pop(); b = pque.top(); pque.pop(); pque.push(2*sqrt(a*b)); k--; } printf("%.3lf\n",pque.top()); return 0; }
- 1
信息
- ID
- 863
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 6
- 已通过
- 1
- 上传者