• Virtual Judge
• ZeroJudge

題意

• 輸入樹名，輸出各樹種佔的比例
• 需要注意的有：
  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;
  }