iT邦幫忙

2021 iThome 鐵人賽

DAY 16
0
自我挑戰組

用 C & C++ 帶你手把手解 UVa 一顆星選集系列 第 16

Day 0x10 UVa10057 A mid-summer nights dream

題意

  • 輸入 n 個數字,輸出能使 (|X1 − A| + |X2 − A| + . . . + |Xn − A|) 得到最小值的 A、最小值數量與最小值有幾種
  • 需要注意的有:
    1. 每筆測資都先輸入 n 個數字 (0 < n ≤ 1000000)
    2. 後面的 n 行為式子中的 x

解法

  • Day 0x4 UVa10041 Vito's Family 13th鐵人賽 uva c c++ 一顆星選集 有 87% 像

    所以一樣教給專業來解釋
    絕對值和最小值發生在X為中位數
    代表說輸出需要的 A 即為中位數

  • 透過 while 重複讀入代表有多少數字的 n,再用 forn 個數字到陣列裡,因為泡沫排序效率太低 (n 有可能很大),就用內建的 qsort 來優化
    int x[1000000];
    
    int compare(const void *a, const void *b){
        return(*(int*)a - *(int*)b);
    }
    
    int main(){
    
        int n;
        int i, j;
    
        while(scanf("%d", &n) != EOF){
    
            for(i = 0; i < n; i++){
                scanf("%d", &x[i]);
            }
    
            qsort(x, n, sizeof(int), compare);
    
            ...
        }
    
        return 0;
    }
    
  • 排序好後即可找中位數,因為有可能 n 的奇偶問題,用兩個變數 A1A2 來分別賦值,至於為什麼這樣寫也留給大家代數字思考看看囉;找好中位數就開始用 for 迴圈計算最小值數量,並用 A2 - A1 + 1 求得有幾種最小值
    A1 = x[(n - 1) / 2];
    A2 = x[n / 2];
    count = 0;
    
    for(i = 0; i < n; i++){
        if(x[i] == A1 || x[i] == A2){
            count++;
        }
    }
    
    printf("%d %d %d\n", A1, count, A2 - A1 + 1);
    
  • C code
    #include<stdio.h>
    #include<stdlib.h>
    
    int x[1000000];
    
    int compare(const void *a, const void *b){
        return(*(int*)a - *(int*)b);
    }
    
    int main(){
    
        int n;
        int A1, A2;
        int count;
        int i, j;
    
        while(scanf("%d", &n) != EOF){
    
            for(i = 0; i < n; i++){
                scanf("%d", &x[i]);
            }
    
            qsort(x, n, sizeof(int), compare);
    
            A1 = x[(n - 1) / 2];
            A2 = x[n / 2];
            count = 0;
    
            for(i = 0; i < n; i++){
                if(x[i] == A1 || x[i] == A2){
                    count++;
                }
            }
    
            printf("%d %d %d\n", A1, count, A2 - A1 + 1);
        }
    
        return 0;
    }
    

上一篇
Day 0xF UVa10071 Back to High School Physics
下一篇
Day 0x11 UVa100 The 3n + 1 problem
系列文
用 C & C++ 帶你手把手解 UVa 一顆星選集30

尚未有邦友留言

立即登入留言