PAT-BASIC1056——组合数的和

我的PAT-BASIC代码仓：https://github.com/617076674/PAT-BASIC

原题链接：https://pintia.cn/problem-sets/994805260223102976/problems/994805271455449088

题目描述：

知识点：排列组合

思路：寻找数学规律

对于每一个数，我们都可以在数组中寻找另一个数构成一个2位数。将这两个数的位置换一下，又是一个新的二位数。假设我们寻找的数是num1和num2，那么可以组成两个2位数，分别是num1 * 10 + num2和num1 + num2 * 10，加起来的和就是(num 1 + num2) * 11。因此，对于每一个组合num1和num2，我们只需要计算(num1 + num2) * 11即可。

时间复杂度是O(N ^ 2)，题目规定了N个非0的个位数字，所以N最大是9，时间复杂度不会太高。空间复杂度是O(1)。

C++代码：

#include<iostream> #include<vector> using namespace std; int main(){ int N; cin >> N; int tempNum; vector<int> nums; for(int i = 0; i < N; i++){ cin >> tempNum; nums.push_back(tempNum); } int sum = 0; for(int i = 0; i < N; i++){ for(int j = i + 1; j < N; j++){ sum += (nums[i] + nums[j]) * 11; } } cout << sum; return 0; }

C++解题报告：