给定两个正整数可能有重复元素的集合,求分别取一元素和为定值的元素对数。
总时间限制: 3000ms 内存限制: 65536kB
给出2个正整数集合A = {pi | 1 <= i <= a},B = {qj | 1 <= j <= b}和一个正整数s。问题是:使得pi + qj = s的不同的(i, j)对有多少个。
第1行是测试数据的组数n,后面跟着n组测试数据。
每组测试数据占5行,第1行是和s (1 <= s <= 10000),第2行是一个正整数a (1 <= a <= 10000),表示A中元素的数目。第3行是a个正整数,每个正整数不超过10000,表示A中的元素。第4行是一个正整数b (1 <= b <= 10000),表示B中元素的数目。第5行是b个正整数,每个正整数不超过10000,表示B中的元素。
注意:这里的集合和数学书上定义的集合有一点点区别——集合内可能包含相等的正整数。
n行,每行输出对应一个输入。输出应是一个非负整数。
2
99
2
49 49
2
50 50
11
9
1 2 3 4 5 6 7 8 9
10
10 9 8 7 6 5 4 3 2 1
4
9
可采用暴力遍历的算法,将集合A中的元素分别与B中的元素求和试探计数即可。
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, i, j, k, a, b, s, num;
cin >> n;
for (i = 0; i < n; ++i) {
cin >> s;
cin >> a;
vector<int> A, B;
for (j = 0; j < a; ++j) {
cin >> num;
if (num < s) {
A.push_back(num);
}
}
cin >> b;
for (j = 0; j < b; ++j) {
cin >> num;
if (num < s) {
B.push_back(num);
}
}
int sum = 0;
for (j = 0; j < A.size(); ++j) {
for (k = 0; k < B.size(); ++k) {
if (A[j] + B[k] == s) {
sum++;
}
}
}
cout << sum << endl;
}
return 0;
}
2792.cpp 代码长度:561B 内存:1152kB 时间:352ms 通过率:95% 最小内存:1024kB 最短时间:14ms
对于集合元素个数未知的情况,可以采用动态内存分配的方式或者使用vector,最后二重循环比较遍历即可。
有任何的改进意见欢迎大家在微信平台公众号主页面留言或者发表issue。