0%

FjnuOJ - 树和堆 - 合并果子

原题:https://fjnuacm.top/d/junior/p/369?tid=6301e681027d8fe886628d9d

感觉之前写得太蠢了就重新写一下(

题意

每次把最小的两个拿出来合并并将数量作为本次体力消耗,输出最小体力消耗值。

思路1

显然,我们只需边枚举边排序,考虑到数据范围够小,暴力是完全可行的。

时间复杂度:

对应AC代码

#include <bits/stdc++.h>

using namespace std;

int d[20001];

int main() {
    int n;
    cin >> n;
    for(int i=0;i<n;i++) cin >> d[i];
    sort(d, d + n);
    int ans = 0;
    for(int i=1;i<n;i++){
        d[i] += d[i - 1];
        ans += d[i];
        sort(d + i, d + n);
    }
    cout << ans << endl;
}

思路2

不难发现,上面暴力的做法无非就是两个步骤:①排序 ②取最小两个加起来放回去

很巧的是,这些步骤完全可以使用封装好的堆结构来实现。

时间复杂度和上述暴力方法完全一致。

时间复杂度:

对应AC代码

import java.util.*;

public class Main{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        int n = scanner.nextInt();
        for(int i=0;i<n;i++) queue.offer(scanner.nextInt());
        int ans = 0;
        while(true){
            if(queue.isEmpty()) break;
            int a = queue.poll();
            if(queue.isEmpty()) break;
            int b = queue.poll();
            queue.offer(a + b);
            ans += a + b;
        }
        System.out.println(ans);
    }
}

堆 = 暴力(暴论