首页 > 试题广场 >

分金条的最小花费

[编程题]分金条的最小花费
  • 热度指数:3906 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个正数数组arr,arr的累加和代表金条的总长度,arr的每个数代表金条要分成的长度。规定长度为k的金条分成两块,费用为k个铜板。返回把金条分出arr中的每个数字需要的最小代价。
[要求]
时间复杂度为,空间复杂度为


输入描述:
第一行一个整数N。表示数组长度。

接下来一行N个整数,表示arr数组。


输出描述:
一个整数表示最小代价
示例1

输入

3
10 30 20

输出

90

说明

如果先分成40和20两块,将花费60个铜板,再把长度为40的金条分成10和30两块,将花费40个铜板,总花费为100个铜板;

如果先分成10和50两块,将花费60个铜板,再把长度为50的金条分成20和30两块,将花费50个铜板,总花费为110个铜板;

如果先分成30和30两块,将花费60个铜板,再把其中一根长度为30的金条分成10和20两块,将花费30个铜板,总花费为90个铜板;

因此最低花费为90
示例2

输入

6
3 9 5 2 4 4

输出

67

备注:




上图可以看做由{3,5,9,2,4,4}构造的最优二叉树,每次选择数组中最小两个数相加并重新添加入数组。直到数组的长度为1。最优二叉树带权路径长度:2*3+3*3+5*2+9*2+4*3+4*3 = 67。当然也可以在构建最优二叉树是计算带权路径长度。
为什么一定是最优二叉树?无论怎样去切割金条,都可以将切割过程画成一颗二叉树,树的叶子是数组中的值,依照该二叉树的切割方案得到花费就是该二叉树的带权路径长度。我们希望得到一个带权路径长度最小的二叉树,那么自然就是最优二叉树。

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[]args)throws IOException{
        BufferedReader b = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(b.readLine());
        long [] arr = new long[n];
        String[]strs = b.readLine().trim().split(" ");

        for(int i= 0; i< n;i++){
            arr[i] = Integer.parseInt(strs[i]);
        }
        b.close();

        
        //计算树的带权路径长度最小值
        PriorityQueue<Long> min = new PriorityQueue<>();//创建一个最小堆,并将所有元素都加入
        for(int i = 0; i<n; i++){
            min.offer(arr[i]);
        }
        long res = 0, combine = 0;
        while(min.size() > 1){//建立最优二叉树,同时计算该树的带权路径长度。
            combine = min.poll() + min.poll();
            res += combine;
            min.offer(combine);
        }
        System.out.println(res);//如果n=1,直接返回0.
    }
}


发表于 2019-09-27 15:52:13 回复(1)
每次合并最小的两个数,构建哈夫曼树,这样能够保证整体的花费是最低的
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Long> pq = new PriorityQueue<>();
        int n = Integer.parseInt(br.readLine());
        String[] strArr = br.readLine().split(" ");
        for(int i = 0; i < n; i++) pq.offer(Long.parseLong(strArr[i]));
        long cost = 0L;
        // 哈夫曼编码过程
        while(pq.size() > 1){
            long temp = pq.poll() + pq.poll();
            cost += temp;
            pq.offer(temp);
        }
        System.out.println(cost);
    }
}

发表于 2021-11-13 16:05:59 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    priority_queue<long, vector<long>, greater<long>> Q;
    long x, cnt=0;
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x;
        Q.push(x);
    }
    while(Q.size()>1){
        x = Q.top();
        Q.pop();
        x += Q.top();
        Q.pop();
        cnt += x;
        Q.push(x);
    }
    cout<<cnt<<endl;
    return 0;
}

发表于 2020-03-13 00:48:03 回复(1)
#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int main()
{
    int n; cin >> n;
    long long num;
    priority_queue<long long, vector<long long>, greater<long long>> minHeap;
    for (int i=0; i<n; i++)
    {
        cin >> num;
        minHeap.push(num);
    }
    long long res = 0;
    long long a, b;
    while (minHeap.size() != 1)
    {
        a = minHeap.top(); minHeap.pop();
        b = minHeap.top(); minHeap.pop();
        res += (a + b);
        minHeap.push(a + b);
    }
    cout << res << endl;
    return 0;
}

发表于 2019-10-15 09:48:24 回复(0)
评论区都在不知所云。给个证明为什么要用哈夫曼树来解决该问题。

证明:

如果每分一段,就视作树的一次成长,树本身的结点值记为当前分段的花费,树两侧的枝视为分开的金条长度。

那么对于这样的树,适合问题最优解的树结构应该是满足非叶子结点和最小的树。

根据https://www.cnblogs.com/FengZeng666/p/12297761.html 的证明,非叶子节点和 等于 WPL即带权路径长度,故而问题变成最优树结构应该满足最小带权路径长度的树,且叶子节点是分成的长度。而满足这个特性的树就是哈夫曼树,哈夫曼树具有这样的特性。


发表于 2024-03-04 10:29:55 回复(0)
public static void main(String[] args) {  int[] arr = {5,10,6,2,10,21}; //1:创建一个小根堆  PriorityQueue<Integer> heap = new PriorityQueue<>(); //2:入堆  for (int i = 0; i < arr.length; i++) {  heap.add(arr[i]); }  //3:一次弹出两个,进行相加,得到的结果进行标注一下,然后再存放在堆中。直到堆里只剩下一个元素循环才停止。  int count = 0; while (heap.size() > 1) {  int cur = heap.poll() + heap.poll();//注意空指针异常。  count += cur;
        heap.add(cur); }  //4:对特殊标注进行相加  System.out.println(count);; }

发表于 2023-12-01 21:45:06 回复(0)
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
using ll = long long;
int main(int argc, char *argv[]) {
	int n;
	cin >> n;
	vector<ll> arr(n,0);
	for(int i = 0;i < n;i++){
		cin >> arr[i];
	}
	priority_queue<ll,vector<ll>,greater<ll>> pq;
    for(const ll& a : arr) pq.push(a);
	ll cur = 0;
	while(pq.size() >= 2){
		ll a = pq.top();
		pq.pop();
		ll b = pq.top();
		pq.pop();
		ll t = a + b;
		pq.push(t);
		cur += t;
	}
	cout << cur  << endl;
}

发表于 2022-02-21 20:47:47 回复(0)
#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;

int main(void){
    int N;
    cin >> N;
    vector<int> v(N);
    priority_queue<long, vector<long>, greater<long>> p;
    for(int i = 0; i < N; i++){
        cin >> v[i];
        p.emplace(v[i]);
    }
    long res = 0;
    while(p.size() >= 2){
        long p1 = p.top();
        p.pop();
        long p2 = p.top();
        p.pop();
        long cur = p1 + p2;
        res += cur;
        p.emplace(cur);
    }
    cout << res << endl;
    return 0;
}
但凡遇到数值累加和问题 都是用long
发表于 2021-05-22 19:36:07 回复(0)
from queue import PriorityQueue as PQue

def get_min_price(list_temp):
    pq = PQue()
    [pq.put(item) for item in list_temp]
    min_price = 0
    while pq.qsize() > 1:
        temp = pq.get() + pq.get()
        min_price += temp
        pq.put(temp)
    return  min_price

n = int(input())
list_a = [int(item) for item in input().split(" ") if item != ""]
print(get_min_price(list_a))

发表于 2020-11-17 19:47:14 回复(0)
import java.util.*;

public class Main{
    
    //使用long,int相加会越界
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine());
        long[] nums = new long[n];
        String[] temp = in.nextLine().split(" ");
        for(int i = 0;i<n;i++){
            nums[i] = Long.parseLong(temp[i]);
        }
        
        //最小堆
        PriorityQueue<Long> pq = new PriorityQueue<>();
        for(long num : nums){
            pq.offer(num);
        }
        
        
        long res = 0;
        while(pq.size()>1){
            //取出两个最小的
            long cost = pq.poll() + pq.poll();
            res += cost;
            pq.offer(cost);
        }
        
        System.out.println(res);
    }
    
    
}

发表于 2020-04-20 11:50:13 回复(0)
哈弗曼编码 。 
涉及到多个int相加,可能会越界。所以最好都用long类型。。
发表于 2020-02-25 17:21:19 回复(0)
#include <iostream>
#include <queue>

using namespace std;

int main(void)
{
    int N;
    long val;
    cin >> N;
    priority_queue<long, vector<long>, greater<long>> heap;
    for (int i = 0; i < N; i++) {
        cin >> val;
        heap.push(val);
    }
    long res = 0;
    while (heap.size() != 1) {
        long a = heap.top(); heap.pop();
        long b = heap.top(); heap.pop();
        res += (a + b);
        heap.push(a + b);
    }
    cout << res << endl;
    return 0;
}

发表于 2020-02-11 18:50:03 回复(0)
#include <queue>
#include <functional>
#include <iostream>
using namespace std;
 
int main()
{
    int len;
    long num, result = 0;
    priority_queue<long, vector<long>, greater<long>> pq;
    cin >> len;
    for (int i = 0; i < len; i++) {
        cin >> num;
        pq.push(num);
    }
    if (len == 1) {
        cout << pq.top() << endl;
        return 0;
    }
    while (pq.size() > 1) {
        long num1 = pq.top();
        pq.pop();
        long num2 = pq.top();
        pq.pop();
        result += (num1 + num2);
        pq.push(num1 + num2);
    }
    cout << result << endl;
    return 0;
}
编辑于 2019-09-09 21:14:26 回复(0)