Nối thanh kim loại

Submit solution
Points: 3
Time limit: 1.0s
Python 3 2.0s
Memory limit: 98M
Python 3 977M
Author:
TICHPX
Problem types
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Công việc cơ khí thật là mệt nhọc, muốn nối một thanh kim loại độ dài a với một thanh kim loại độ dài b thì kinh phí để thuê nối tốn mất a+b đơn vị tiền tệ. Hiện nay Tichpx cần nối n thanh kim loại lần lượng có độ dài là a1,a2, ... an thành một đoạn theo bạn Tichpx nên bố trí thế nào để tổng số tiền phải trả là ít nhất

Input

Dòng đầu chứa số nguyên dương n \((1<=n<=10^5)\)

Dòng tiếp theo là n số nguyên dương tương ứng là độ dài các thanh muốn nối \((1<= a_i <= 10^3)\)

Output

Một số nguyên dương là số kinh phí ít nhất phải trả

Ví dụ

Input

3
8 4 6

Output

28

Giải thích : Nếu ta nối thanh 8 với thanh 4 tốn chi phí là 8+4=12 sau khi nối xong còn 2 thanh độ dài 12 và 6 nối lại với nhau tốn 12+6=18 tổng chi phí nối là 12+18=30. Nếu ta nối 4 với 6 trước tốn 10 và còn 2 thanh 10 và 8 nối lại với nhau tốn 18 do đó tổng kinh phí ít hơn chỉ còn 28

tichpx

Comments


  • 0
    LãoTam  commented on Nov. 3, 2021, 1:59 a.m. ← edited

    [user:^_^]Tham khảo ý tưởng

    b1: do cần tổng chi phí nối thanh kim loại nhỏ nhất=> mỗi lần lấy 2 số nhỏ nhất=>bản thân tổng sau khi đưa vào hàng đợi cũng phải được sắp xếp tăng dần=> dùng hàng đợi ưu tiên prioritty_queue
b2: lấy gtri va loại bỏ 2 số min của hàng đợi
b3: lấy tổng 2 số đó và đưa vào hàng đợi, cập nhật s1 chính là kqua cần tìm +=s
b4: nếu như hàng đợi rỗng thì kết thúc vòng lặp
    #include<bits/stdc++.h>
using namespace std;

void initwolve(){
    int n;cin>>n;
priority_queue<int,vector<int>,greater<int>>pq;
int a[n];
for(int i=0;i<n;i++){
    cin>>a[i];
    pq.push(a[i]);
    }
    long long p,q,s=0,s1=0;
    while(pq.size()){
        p=pq.top(); pq.pop();
        q=pq.top();pq.pop();
        s=p+q;
        s1+=s;
        if(pq.size()==0) break;
        pq.push(s);
        }
        cout<<s1;
            }
int main()
{
initwolve();

}