1 条题解

  • 0
    @ 2025-5-22 14:35:33

    这段代码解决的是 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
    上传者