Lắp ghép ống nước

Submit solution
Points: 2
Time limit: 1.0s
Python 3 2.0s
Memory limit: 1000M
Author:
TICHPX
Problem type
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

Thành phố xây dựng hệ thống nước sạch cần phải lắp ghép các đoạn ống có độ dài lần lượt là a1,a2, … an thành một đường ống thẳng, để lắp ghép cần một máy nâng nhưng khả năng của nó mỗi lúc chỉ nối được tối đa k đoạn ống và chi phí để nối chính là tổng độ dài của đoạn đó sau khi nối. Bạn hãy lập trình tính tổng chi phí nối là ít nhất

Input

Dòng thứ nhất chứa hai số nguyên dương n và k (1< k < n <=10^5)

Dòng tiếp theo chứa n số nguyên dương là độ dài của n đoạn ống cần nối có giá trị không vượt quá 3*10^4

Output

Một số nguyên dương duy nhất là tổng số chi phí ít nhất để nối hệ thống cấp nước

Ví dụ 1:

Input

3 2
8 4 6

Output

28

Giải thích: Mỗi bước chỉ nối tối đa được 2 đoạn, nếu ta nối 8 với 4 tốn chi phí là 8+4=12 sau khi nối xong còn 2 đoạn độ 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 đoạn 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.

Ví dụ 2:

Input

6 3
8 2 1 5 2 3

Output

39

Giải thích:

Bước 1: lắp các đoạn 1+2+2 tốn 5 bây giờ sẽ giảm đi 1, 2, 2 và thêm vào đoạn 6 nên còn các đoạn 8,5,3,5

Bước 2: lắp các đoạn 5+3+5 tốn 13 bây giờ sẽ giảm đi 5, 3, 5 và thêm vào đoạn 13 nên còn các đoạn 8, 13

Bước 3: lắp nốt 8+13 tốn 21

Tổng chi phí 5+13+21 = 39

tichpx

Comments


  • 3
    DuyAnhhh  commented on Sept. 27, 2020, 12:36 p.m.

    Easy with priority_queue ^^


  • -2
    181500678  commented on Sept. 7, 2019, 12:37 p.m. ← edited 
    #include "stdio.h"
#define swap(x,y) x^=y^=x^=y
void sortAll(int n,long arr[]);
long count(int n,int k,long arr[]);
void sortLocal(int n,long arr[]);
int main(){
    int n,i,k;
    long arr[100];
    scanf("%d%d",&n,&k);
    for(i=0;i<n;i++) scanf("%ld",&arr[i]);
    sortAll(n,arr);//do dai cua mang     
    printf("%ld",count(n,k,arr));//do dai mang    
}
void sortAll(int n,long arr[]){
    for(int i=n-1;i>0;i--){ //chi so thuc
        for(int j=i-1;j>=0;j--){
            if(arr[i]>arr[j]) swap(arr[i],arr[j]);
        }
    }
}
void sortLocal(int n,long arr[]){
    for(int i=n;i>0;i--) if(arr[i]>arr[i-1]) swap(arr[i],arr[i-1]); else return; //chi so thuc
}
long count(int n,int k,long arr[]){
    long cost=0;
    if(n==1) return 0;
    if(n<k){
        for(int i=0;i<n;i++) cost+=arr[i];
        return cost;
    }
    else{   
    for(int i=1;i<=k;i++){
        cost+=arr[n-i];
    }
    arr[n-k]=cost;
    sortLocal(n-k,arr);// sau khi loai bo k-1 phan tu
    return cost+count(n-k+1,k,arr);//do dai mang sau khi loai bo k-1 phan tu        
    }
}

    lỗi RTE ở đâu vậy mn.


    • 1
      TheDemonTuan  commented on Sept. 13, 2019, 12:04 p.m.

      Câu này dùng min heap giải nhé :v