【PAT甲級】Friend Numbers

2019 年 11 月 8 日
筆記

本文鏈接：https://blog.csdn.net/weixin_42449444/article/details/89451403

Problem Description：

Two integers are called "friend numbers" if they share the same sum of their digits, and the sum is their "friend ID". For example, 123 and 51 are friend numbers since 1+2+3 = 5+1 = 6, and 6 is their friend ID. Given some numbers, you are supposed to count the number of different frind ID's among them.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N. Then N positive integers are given in the next line, separated by spaces. All the numbers are less than 104.

Output Specification:

For each case, print in the first line the number of different frind ID's among the given integers. Then in the second line, output the friend ID's in increasing order. The numbers must be separated by exactly one space and there must be no extra space at the end of the line.

Sample Input:

8  123 899 51 998 27 33 36 12

Sample Output:

4  3 6 9 26

解題思路：

這題在乙級里寫過：【PAT乙級】朋友數。先自定義一個fun()函數用來求各位數之和，建立一個set用來記錄朋友證號，然後無腦雙重for循環，當倆個數的各位數之和相等的時候就說明它們倆個是朋友數存入set中。然而我第一次提交之後有個測試點TLE了，於是我在雙重for循環中加入了一條if語句，如果set中已經記錄過了這個朋友證號就可以不用再進行第二層for循環了，提交之後AC啦。

AC程式碼：

#include <bits/stdc++.h>  using namespace std;    int fun(int n)  //用來求各位數之和  {      string temp = to_string(n);      int sum = 0;      for(auto it : temp)      {          sum += it-'0';      }      return sum;  }    int main()  {      int N;      cin >> N;      int a[N];      for(int i = 0; i < N; i++)      {          cin >> a[i];      }      set<int> s;  //用來記錄朋友證號      for(int i = 0; i < N; i++)      {          int temp = fun(a[i]);          if(s.count(temp) == 0)  //第一次遞交後出現了TLE,然後我加了這條if語句,不再考慮出現過的朋友證號          {              for(int j = i; j < N; j++)              {                  if(temp == fun(a[j]))  //兩個數的各位數之和相等,它們就是朋友數                  {                      s.insert(temp);                  }              }          }      }      cout << s.size() << endl;    //set.size()就是朋友證號的個數      bool isVirgin = true;  //判斷是不是第一次      for(auto it : s)   //無腦遍歷set進行輸出      {          if(isVirgin)          {              cout << it;              isVirgin = false;          }          else          {              cout << " " << it;          }      }      return 0;  }