给定一个正数数组arr,arr的累加和代表金条的总长度,arr的每个数代表金条要分成的长度。规定长度为k的金条分成两块,费用为k个铜板。返回把金条分出arr中的每个数字需要的最小代价。
[要求]
时间复杂度为
,空间复杂度为![](https://uploadfiles.nowcoder.com/files/20190201/310694_1549028155714_equation?tex=O(n))
第一行一个整数N。表示数组长度。
接下来一行N个整数,表示arr数组。
一个整数表示最小代价
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
6 3 9 5 2 4 4
67
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); } }
#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; }
#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; }
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. } }
证明:
如果每分一段,就视作树的一次成长,树本身的结点值记为当前分段的花费,树两侧的枝视为分开的金条长度。
那么对于这样的树,适合问题最优解的树结构应该是满足非叶子结点和最小的树。
根据https://www.cnblogs.com/FengZeng666/p/12297761.html 的证明,非叶子节点和 等于 WPL即带权路径长度,故而问题变成最优树结构应该满足最小带权路径长度的树,且叶子节点是分成的长度。而满足这个特性的树就是哈夫曼树,哈夫曼树具有这样的特性。
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);; }
#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; }
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))
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); } }
#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; }
#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; }