題組內容

四、超商預計發展合併集點卡程式，說明如下。若有 n 張集點卡要合併，但只 能兩張兩張合併，因此共需合併 n-1 次才能把點數全部集中到一張卡。2 張合併時會扣掉較少點數那張的 1/10 點數（無條件進位至整數）做為手 續費。例如，若有 A, B, C 3 張集點卡要合併，且點數分別為 25, 30, 51 點。若先合併 A, B，再合併 C，則會扣掉 3+6 點，因此合併後剩 97 點， 這也剛好是最差合併策略下的合併總點數；但在最佳的合併策略下（先 合併 B, C，再合併 A），則可有 100 點。

(一)請寫 best_case() 函式，計算 n 張集點卡合併過後最多可有多少點數。

詳解 (共 1 筆)

詳解 提供者：Fourier
也不清楚可不可以多插一個標頭檔
用ceil四捨五入比較方便
不插math.h的話可以用剛剛問chatgpt的方法a=(b+9)/10挺有趣的

#include<stdio.h>
#include<math.h>
int a[101],n;
int best_case(){
    for(int i=0;i<n;i++){      \\我也不知道我qsort為啥不能用索性寫個氣泡排序
        for(int j=0;j<n;j++){
            if(a[j]<a[j+1]){
                int temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
    int sum=a[0],min=0;
    for(int i=1;i<n;i++){
        float temp=a[i];
        sum=sum+a[i]-ceil(temp/10); \\無條件進位
    }
    return sum;
}
int worst_case(){
    int sum=a[n-1];
    for(int i=n-2;i>=0;i--){
        float temp=a[i];
        sum=sum+a[i]-ceil(temp/10);
    }
    return sum;
}
 
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]); \\題目有問題沒加&
    }
    printf("Best case: %d points\n",best_case());
    printf("Worst case: %d points\n", worst_case());
    return 0;
}