2022 年 11 月 3 日

C, C++, Python, ZJ解題

d221: Add All

2022.11.03 PM 11:50 by CBJ

來源 : https://zerojudge.tw/ShowProblem?problemid=d221
出題者 : UVa
標籤 : 貪心、排序、二分搜尋法、優先佇列
難易度 : 4

解題想法 : 
。C/Python - 排序，之後每次取出前兩項(最小兩個)相加，並使用二分搜找到放回的點，重覆實作直到剩下一項為止，過程紀錄ans。
。C++/Python - 每次拿最前面兩個數相加後放回priority_queue/heapq，直到剩下一個為止，過程記錄ans

//C language
//solution link(含註解): https://github.com/CBJ0519/CBJsProgramDiary.com/blob/main/zj/d221.c
#include<stdio.h>
#include<stdlib.h>
#include<string.h> 
int cmp(const void *a,const void *b){
    return *(int*)a - *(int*)b;
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        if(n==0) break;
        int digits[10005]; 
        memset(digits,-1,sizeof(digits)); 
        for(int i=0;i<n;i++){
            scanf("%d",&digits[i]);  
        }
        qsort(digits,n,sizeof(int),cmp);
        long long ans=0;
        int lcnt=0, rcnt=n;
        while((rcnt - lcnt) > 1){
            int a=digits[lcnt];
            digits[lcnt++]=-1;  
            int b=digits[lcnt];
            digits[lcnt++]=-1;
            ans+=(a+b);
            int L=lcnt-1,R=rcnt;
            while(R-L > 1){
                int m=(L+R)>>1;
                if(digits[m] > (a+b)) R=m;
                else L=m;
            }
            for(int i=rcnt;i>R;i--) digits[i]=digits[i-1];
            digits[R]=(a+b);
            rcnt++;
        }
        printf("%lld\n",ans);  
    }
    return 0;
}

//C++ language
//solution link(含註解): https://github.com/CBJ0519/CBJsProgramDiary.com/blob/main/zj/d221.cpp
#include<iostream>
#include<algorithm> 
#include<queue>  
using namespace std;
int main(){
    int n;
    while(cin>>n){
        if(!n) break;  priority_queue<int,vector<int>,greater<int>>digits;  
        for(int i=0;i<n;i++){
            int x; cin>>x;
            digits.push(x);
        }
        long long ans=0;
        while(digits.size()>1){
            int a=digits.top();
            digits.pop();
            int b=digits.top();
            digits.pop();
            ans+=(a+b);
            digits.push(a+b);
        }
        cout<<ans<<"\n"; 
    }
    return 0;
}

## Python language
## solution link(含註解): https://github.com/CBJ0519/CBJsProgramDiary.com/blob/main/zj/d221.py
from sys import stdin
from bisect import insort 
for read in stdin: 
    n=int(read)  
    if n==0: break   
    digit=[int(x) for x in input().split()]
    digit.sort()  
    ans=0   
    while len(digit)>1: 
        a=digit.pop(0)  
        b=digit.pop(0)
        ans+=(a+b)  
        insort(digit,a+b)  
    print(ans)

相關文章

發佈留言取消回覆