PAT乙级1064 || 朋友数（详解，C/C++示例，测试点分析）

Posted on In

朋友数

题目描述

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

输入格式

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

输出格式

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

输入样例

1
2
8
123 899 51 998 27 33 36 12

输出样例

1
2
4
3 6 9 26

问题解决

解题思想

本题采用C++标准模板库（STL）的set容器可以很方便的解决。set容器的简单介绍请看下面的知识拓展。在输入的同时计算每个整数的朋友证号并将其加入set中即可，由于set本身会自动递增排序并去重，因此，去重和排序就不必我们亲自去实现了。

由题给样例可知，不一定要两个或两个以上的整数的朋友证号相同才统计输出，若某整数的朋友证号是唯一的，也要统计输出的。

知识拓展

set容器内元素的两个很重要的特性是：

  • 自动递增排序
  • 自动去除重复元素

使用set之前要添加上#include <set>与using namespace std;。

set的定义（以定义int和char型为例）：

1
2
set <int> st;
set <char> st;

set容器内元素的访问只能通过迭代器访问，如代码示例的输出。定义迭代器，按如下方式进行：

1
2
set <int> :: iterator it;	//it即为迭代器变量，初学者可按指针来理解
it = st.begin();	//给迭代器变量赋值，st.begin()为st的首元素地址，尾元素的下一个地址为st.end()

遍历整个st可用如下方式：

1
2
3
for(set <int>::iterator it = st.begin(); it != st.end(); it++) {
    //visit
}

st.size()是获得st内元素的个数。

更多相关set的内容，请自行查阅相关书籍。

代码示例（C/C++）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cstdio>
#include <set>
using namespace std;
int Friend_ID(int a);
int main() {
    set <int> st;   //set容器的定义
    int n;
    scanf("%d", &n);
    while(n--) {
        int tmp;
        scanf("%d", &tmp);
        st.insert(Friend_ID(tmp));
    }
    printf("%d\n", st.size());
    int flag = 1;   //控制输出格式的标记
    for(set <int>::iterator it = st.begin(); it != st.end(); it++) {
        if(flag) {
            printf("%d", *it);
            flag = 0;
        }
        else {
            printf(" %d", *it);
        }
    }
    return 0;
}
//计算整数a的朋友证号
int Friend_ID(int a) {
    int sum = 0;
    while(a) {
        sum += a % 10;
        a /= 10;
    }
    return sum;
}

题目来源：PAT乙级1064
作者：CHEN, Yue
单位：浙江大学

稀罕作者