iT邦幫忙

2021 iThome 鐵人賽

DAY 28
0
自我挑戰組

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

Day 0x1C UVa10420 List of Conquests

  • Virtual Judge
  • ZeroJudge
    • 沒中文 QAQ
    • 簡單講一下,就是有一個大情聖,要記錄他的魚池攻略本,原本是用時間順序紀錄,現在為了方便要照國籍與姓名重新排序

題意

  • 輸入國家和人名,輸出國名與人數
  • 需要注意的有:
    1. 第一行輸入整數 n 代表人數 (最多 2000)
    2. 接下來的 n 行輸入每個人的國籍與名字 (最多 75 個字元)
    3. 國籍是一個單字
    4. 按照國籍的英文字母排序,輸出國籍與該國人數
  • 隱藏要點:
    • 國籍只有一個單字,但名字不會

解法

  • 先讀入人數 n 後,用 while 迴圈重複輸入國名與人名存到二維字元陣列中,因為可能包含空白,所以用 gets(),但因為人名其實不重要 (因為是要求各國人數),每次都覆蓋過去即可
    int n;
    int i;
    char country[2001][76] = {0};
    char name[76] = {0};
    
    scanf("%d", &n);
    
    for(i = 0; i < n; i++){
        scanf("%s", country[i]);
        gets(name);
    }
    
  • 透過 strcmp 能夠比較字典序的特性 (回傳值會不同),用簡單的泡沫排序來實作
    for(i = 0; i < n - 1; i++){
        for(j = 0; j < n - 1 - i; j++){
            if(strcmp(country[j], country[j + 1]) > 0){
                strcpy(temp, country[j]);
                strcpy(country[j], country[j + 1]);
                strcpy(country[j + 1], temp);
            }
        }
    }
    
  • 針對國名排序好後,透過 flag 的狀態來控制輸出國名或次數
    • while 迴圈及 i 變數來遍歷字元陣列
    • 如果 flag == false 就輸出國名,並改變狀態開始計算次數
    • 如果 flag == true 且當前國名和下個國名相同 (回傳值是 0) 就繼續累加;反之則輸出次數並初始 flag 及次數
    flag = false;
    count = 0;
    i = 0;
    
    while(i < n){
        if(!flag){
            printf("%s ", country[i]);
            count++;
            flag = true;
        }
        else if(flag){
            if(strcmp(country[i], country[i + 1]) == 0){
                count++;
            }
            else{
                printf("%d\n", count);
                flag = false;
                count = 0;
            }
            i++;
        }
    }
    
  • C code
    #include<stdio.h>
    #include<string.h>
    #include<stdbool.h>
    
    int main(){
    
        int n;
        int i, j;
        int count, flag;
        char country[2001][76] = {0};
        char name[76] = {0};
        char temp[76] = {0};
    
        scanf("%d", &n);
    
        for(i = 0; i < n; i++){
            scanf("%s", country[i]);
            gets(name);
        }
    
        for(i = 0; i < n - 1; i++){
            for(j = 0; j < n - 1 - i; j++){
                if(strcmp(country[j], country[j + 1]) > 0){
                    strcpy(temp, country[j]);
                    strcpy(country[j], country[j + 1]);
                    strcpy(country[j + 1], temp);
                }
            }
        }
    
        flag = false;
        count = 0;
        i = 0;
    
        while(i < n){
            if(!flag){
                printf("%s ", country[i]);
                count++;
                flag = true;
            }
            else if(flag){
                if(strcmp(country[i], country[i + 1]) == 0){
                    count++;
                }
                else{
                    printf("%d\n", count);
                    flag = false;
                    count = 0;
                }
                i++;
            }
        }
    
        return 0;
    }
    
  • C++
    • 非常適合用 map 來實作,因為每個元素都唯一且排序,直接 key 放國名,value 放次數
      • 插入可用 .insert().emplace() 都可以;遍歷也可改用 iterator 的標準寫法
    • map
    #include <bits/stdc++.h>
    using namespace std;
    
    int main(){
    
        int n;
        string str;
        map<string, int> mp;
    
        cin >> n;
    
        while(n--){
            cin >> str;
            mp[str]++;
            getline(cin, str);
        }
    
        for(auto i: mp){
            cout << i.first << " " << i.second << endl;
        }
    
        return 0;
    }
    

上一篇
Day 0x1B UVa10922 2 the 9s
下一篇
Day 0x1D UVa10226 Hardwood Species
系列文
用 C & C++ 帶你手把手解 UVa 一顆星選集30

尚未有邦友留言

立即登入留言