A27932. 乘积的最大和给定两组整数 A 和 B，你可以从 A 中任选一个整数，与 B 中任选的一个整数相乘。注意每个整数至多只能被选中 1 次。将这些乘积加起来，最大值能达到多少？输入输入第一行给出正整数 NA，为 A 组中整数的个数，随后一行给出 A 中的 NA 个整数；然后给出正整数 NB，为 B 组中整数的个数，随后一行给出 B 中的 NB 个整数。数据范围为 1 ≤ NA, NB ≤ 105，最大…
填空题
较难
知识点
题目描述
乘积的最大和
给定两组整数 A 和 B，你可以从 A 中任选一个整数，与 B 中任选的一个整数相乘。注意每个整数至多只能被选中 1 次。将这些乘积加起来，最大值能达到多少？
输入
输入第一行给出正整数 NA，为 A 组中整数的个数，随后一行给出 A 中的 NA 个整数；然后给出正整数 NB，为 B 组中整数的个数，随后一行给出 B 中的 NB 个整数。数据范围为 1 ≤ NA, NB ≤ 105，最大答案不超过 230。
输出
在一行中输出题面要求的乘积和的最大值。
样例输入
4
1 2 4 -1
4
7 6 -2 -3样例输出
43样例解释： 43 = (-1)×(-3)+4×7+2×6
参考答案
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int na, nb;
vector<int> A_pos, A_neg, B_pos, B_neg;
cin >> na;
for (int i = 0; i < na; ++i) {
int x;
cin >> x;
if (x > 0) {
A_pos.push_back(x);
} else if (x < 0) {
A_neg.push_back(x);
}
}
cin >> nb;
for (int i = 0; i < nb; ++i) {
int x;
cin >> x;
if (x > 0) {
B_pos.push_back(x);
} else if (x < 0) {
B_neg.push_back(x);
}
}
sort(A_pos.rbegin(), A_pos.rend());
sort(A_neg.begin(), A_neg.end());
sort(B_pos.rbegin(), B_pos.rend());
sort(B_neg.begin(), B_neg.end());
int i = 0, j = 0, k = 0, l = 0;
long long sum = 0;
while (true) {
long long pos_prod = 0, neg_prod = 0;
bool pos_valid = false, neg_valid = false;
if (i < A_pos.size() && j < B_pos.size()) {
pos_prod = (long long)A_pos[i] * B_pos[j];
pos_valid = true;
}
if (k < A_neg.size() && l < B_neg.size()) {
neg_prod = (long long)A_neg[k] * B_neg[l];
neg_valid = true;
}
if (!pos_valid && !neg_valid) {
break;
}
if (pos_valid && neg_valid) {
if (pos_prod >= neg_prod) {
sum += pos_prod;
i++;
j++;
} else {
sum += neg_prod;
k++;
l++;
}
} else if (pos_valid) {
sum += pos_prod;
i++;
j++;
} else {
sum += neg_prod;
k++;
l++;
}
}
cout << sum << endl;
return 0;
}
上一题
下一题