Nối thanh kim loại


Submit solution

Points: 3
Time limit: 1.0s
Pypy 3 5.0s
Python 3 5.0s
Memory limit: 977M

Author:
Problem types

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


  • 1
    DoHoangTuBap  commented on March 8, 2021, 10:12 p.m. edited
    // noi cac thanh kim loai
    #include<bits/stdc++.h>
    using namespace std;
    
    int main(){
        priority_queue<int, vector<int>, greater<int> >Q;
        int n,x;
        cin>>n;
        while(n--) {cin>>x; Q.push(x);}
        while(Q.size()>1)
        {
            int u=Q.top(); Q.top();
            int v=Q.top(); Q.top();
            res+=u+v;
            Q.push(u+v);
    
        }
        cout>>res;
    }

  • -4
    2000cntt2k59  commented on June 20, 2020, 10:56 p.m. edit 2
    #include<bits/stdc++.h>
    using namespace std;
    struct Tre
    {
    int a,b,M;
    Tre *L,*R;
    Tre(int u,int v)
    {
    
    a=u,b=v,M=b-a; L=R=0;
    }
    };
    int update(Tre *T,int k)
    {
    if(T->L==0) {T->L=new Tre(T->a,k); T->R=new Tre(k,T->b);}
    else T->L->b>k?update(T->L,k):update(T->R,k);
    return T->M=max(T->L->M,T->R->M);
    }
    void inorder(Tre *T,string p="\n")
    {
    if(!T) return;
    inorder(T->L,p+"\t\t");
    cout<<p<<"{"<<T->a<<","<<T->b<<","<<T->M<<"}";
    inorder(T->R,p+"\t\t");
    }
    int main()
    {
    int a[]={13,8,17,5,9};
    Tre *T=new Tre(0,20);
    for(int k:a) cout<<"\nCat "<<k<<" max "<<update(T,k);
    inorder(T);
    }