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 能够比较字典序的特性 (回传值会不同)，用简单的泡沫排序来实作
  • 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;
  }