问题 K: Length of Bundle Rope

技术文章 1年前 (2020) 完美者
1,961 0

标签:sep   page   transport   span   tran   pack   contain   second   提交   

问题 K: Length of Bundle Rope

时间限制: 2 Sec  内存限制: 1024 MB
提交 状态

题目描述

Due to the development of online shopping, the logistics industry which is highly connected with goods shipping has been so prosperous that the great amount of employees is needed.

Therefore, Alex, a truck driver in this growing industry, was supposed to transport several parcels scattering in the warehouse to other cities in his daily routine.

According to the o?icial safety requirements to the trucks running in the highway, Alex had to tie up all the packages tightly so that he could settle the goods safely on his truck. Alex knew that the length of the cords needed for bundling the packages on the truck was based on the size of the packages themselves. Also, n packages can be tied up well after n ? 1 bundles.

Moreover, when bundling goods, Alex could only bundle two packages at one time to avoid scattering. Since the daily consumption of the cord was great and Alex was supposed to pay for it, he hopes to bundle all the goods with the shortest cord.

For example, there are 4 parcels in the size of 8, 5, 14, and 26 respectively. If Alex binds the first two together, the needed rope will be in the length of 13( 8+5 = 13) while the needed rope for the latter two packages will be 40 (14 + 26 = 40). If Alex keeps bundling these two items,the rope length he needs will be 53 (13 + 40 = 53). So the total length of the 4 packages will

be 106 (13 + 40 + 53 = 106). If Alex tries another way by bundling the first two( 8 + 5 = 13),adding up the third one (13 + 14 = 27), and then bundling the last item (27 + 14 = 53), he will only need the cord in the length of 93 (13 + 27 + 53 = 93). Now your mission is to help Alex finding the minimum length of the needed cord.

输入

The first line contains an integer T indicating the number of test cases. Each test case contains two lines. The first one contains a positive integer n indicating the number of packages. The second one contains n positive integers separated by a space to indicate the size of each parcel.

输出

For each test case, output the minimum length of the bundle rope required to tie all parcels together in one line.

样例输入 Copy

4
6
2 3 4 4 5 7
5
5 15 40 30 10
10
3 1 5 4 8 2 6 1 1 2
9
3 2 1 6 5 2 6 4 3

样例输出 Copy

63
205
100
98

提示

? 1 ≤ T ≤ 10

? 1 ≤ n ≤ 1000

? The size of each parcel is at most 1000.

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int t, n;

int main(){
    scanf("%d", &t);
    
    while(t -- ){
        scanf("%d", &n);
        priority_queue<int ,vector<int>, greater<int>> q;
        
        while (n -- ){
            int x;
            scanf("%d", &x);
            q.push(x);
        }
        
        long long res = 0;
        while (q.size() > 1){
            int x = q.top(); q.pop();
            int y = q.top(); q.pop();
            res += x + y;
            q.push(x + y);
        }
        
        printf("%lld\n", res);
    }
    
    return 0;
}

  

问题 K: Length of Bundle Rope

标签:sep   page   transport   span   tran   pack   contain   second   提交   

原文地址:https://www.cnblogs.com/Iamcookieandyou/p/13656615.html

版权声明:完美者 发表于 2020-09-17 22:58:33。
转载请注明:问题 K: Length of Bundle Rope | 完美导航

暂无评论

暂无评论...