【PAT乙级】朋友数

正文索引 [隐藏]

题目描述:

如果两个整数各位数字的和是一样的,则被称为是“朋友数”,而那个公共的和就是它们的“朋友证号”。例如 123 和 51 就是朋友数,因为 1+2+3 = 5+1 = 6,而 6 就是它们的朋友证号。给定一些整数,要求你统计一下它们中有多少个不同的朋友证号。

输入描述:

输入第一行给出正整数 N。随后一行给出 N 个正整数,数字间以空格分隔。题目保证所有数字小于 10​4​​。

输出描述:

首先第一行输出给定数字中不同的朋友证号的个数;随后一行按递增顺序输出这些朋友证号,数字间隔一个空格,且行末不得有多余空格。

输入样例:

8
123 899 51 998 27 33 36 12

输出样例:

4
3 6 9 26

解题思路:

先自定义一个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;
}