iT邦幫忙

2021 iThome 鐵人賽

DAY 29
0
自我挑戰組

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

Day 0x1D UVa10226 Hardwood Species

題意

  • 輸入樹名,輸出各樹種佔的比例
  • 需要注意的有:
    1. 第一行輸入正整數 n 代表測資數
    2. 每筆輸入及輸出之間皆有空白行
    3. 每行輸入代表一顆樹,樹名不超過 30 個字元;樹種不超過 10000;數量不超過 1000000
    4. 輸出按照字典序,經過排序後的樹名及比例 (小數點後四位)

解法

  • 輸入代表測資數的整數 n,兩次 getchar() 分別濾掉換行與空白行,再開始用 while 迴圈重複輸入
    int n;
    
    scanf("%d", &n);
    getchar();
    getchar();
    
    while(n--){
        ...
    }
    
  • 因為 1000000 X 31 的陣列太大,所以宣告成全域變數,因此每次都要記得先清空陣列;之後再用 for 迴圈讀入樹名直到空白行 (輸入後仍為 0);同時計算共有多少顆樹,存到 num 裡面
    int num = 0;
    
    for(i = 0; i < 1000000; i++){
        memset(name[i], 0, 31);
    }
    
    for(i = 0; ;){
        gets(name[i]);
        if(name[i][0] == 0){
            break;
        }
        else{
            i++;
            num++;
        }
    }
    
  • 雖然一樣是按照字典序排序,但是不能像 Day 0x1C UVa10420 List of Conquests 寫成泡沫排序,所以使用 qsort() 來加速
    int compare(const void * a, const void * b){
    
        int flag = strcmp(a, b);
    
        if(flag > 0){
            return 1;
        }
        else if(flag < 0){
            return -1;
        }
        else{
            return 0;
        }
    
    }
    int main(){
        ...
        qsort (name, num, 31, compare);
        ...
    }
    
  • 輸出時和 Day 0x1C UVa10420 List of Conquests 同概念,使用 flag 的狀態來決定是否輸出與計算次數;要小心輸出型態是四位數與測資間的空白行
    for(i = 0; i < num;){
        if(!flag){
            printf("%s ", name[i]);
            flag = true;
            count++;
        }
        else{
            if(i + 1 != num && strcmp(name[i], name[i + 1]) == 0){
                count++;
            }
            else{
                printf("%.4lf\n", ((double)count / (double)num) * 100);
                flag = false;
                count = 0;
            }
            i++;
        }
    }
    
    if(n){
        printf("\n");
    }
    
  • C code
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<stdbool.h>
    
    char name[1000000][31];
    
    int compare(const void * a, const void * b){
    
        int flag = strcmp(a, b);
    
        if(flag > 0){
            return 1;
        }
        else if(flag < 0){
            return -1;
        }
        else{
            return 0;
        }
    
    }
    
    int main(){
    
        int n;
        int i, j;
    
        scanf("%d", &n);
        getchar();
        getchar();
    
        while(n--){
    
            char temp[31] = {0};
            int num = 0;
            bool flag = false;
            int count = 0;
    
            for(i = 0; i < 1000000; i++){
                memset(name[i], 0, 31);
            }
    
            for(i = 0; ;){
                gets(name[i]);
                if(name[i][0] == 0){
                    break;
                }
                else{
                    i++;
                    num++;
                }
            }
    
            qsort (name, num, 31, compare);
    
            for(i = 0; i < num;){
                if(!flag){
                    printf("%s ", name[i]);
                    flag = true;
                    count++;
                }
                else{
                    if(i + 1 != num && strcmp(name[i], name[i + 1]) == 0){
                        count++;
                    }
                    else{
                        printf("%.4lf\n", ((double)count / (double)num) * 100);
                        flag = false;
                        count = 0;
                    }
                    i++;
                }
            }
    
            if(n){
                printf("\n");
            }
        }
    
        return 0;
    }
    
  • C++
    • 神奇的 map 又登場了,要注意輸出格式即可
    #include <bits/stdc++.h>
    using namespace std;
    
    int main(){
    
        int n;
        bool flag = false;
        string name;
    
        cin >> n >> ws;
        // 這幾種方法都行,濾掉多餘換行
        // cin.get();
        // cin.ignore();
        // getline(cin, name);
    
        while(n--){
    
            if(flag){
                cout << "\n";
            }
    
            flag = true;
            double sum = 0;
            map<string, int> mp;
    
            while(getline(cin, name) && name != ""){
                mp[name]++;
                sum++;
            }
    
            for (auto i: mp){
                cout << i.first << " " << fixed << setprecision(4) << (i.second / sum) * 100 << "\n";
            }
        }
    
        return 0;
    }
    

上一篇
Day 0x1C UVa10420 List of Conquests
下一篇
Day 0x1E UVa11321 Sort! Sort!! and Sort!!!
系列文
用 C & C++ 帶你手把手解 UVa 一顆星選集30

尚未有邦友留言

立即登入留言