1037. Magic Coupon.md

【PAT A-1037】Magic Coupon

题意概述

给定两个序列，从这两个序列中每次分别拿出一个数字进行相乘，问最终得到的所有乘积之和最大是多少。序列中每个数字最多只能用一次，当然也可以不用。

输入输出格式

输入第一行先给出第一个序列的长度$N_c$，然后是$N_c$个整数。第二行先给出第二个序列的长度$N_p$，然后是$N_p$个整数。

输出最终得到的所有乘积之和的最大值。

数据规模

$$1\le N_c,N_p\le{10}^5$$

算法设计

解决这道题需要使用贪心算法，贪心策略是：对两个序列进行排序，正数和负数分开考虑，对于正数，肯定是大的整数乘大的正数得到的乘积更大；对于负数，肯定是小的负数乘小的负数得到的乘积更大。

注意点

进行累加的循环中，不能以乘积大于 0 或者乘积小于 0 作为判断条件，因为在两个序列正负数个数相同时，这样的求得的结果会发生错误（想一想为什么？）。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ni, mi;
    cin >> ni;
    vector<gg> v1(ni);
    for (gg& i : v1) {
        cin >> i;
    }
    cin >> mi;
    vector<gg> v2(mi);
    for (gg& i : v2) {
        cin >> i;
    }
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    gg ans = 0;
    for (gg i = 0; i < min(ni, mi) and v1[i] < 0 and v2[i] < 0; ++i) {
        ans += v1[i] * v2[i];
    }
    for (gg i = ni - 1, j = mi - 1;
         i >= 0 and j >= 0 and v1[i] > 0 and v2[j] > 0; --i, --j) {
        ans += v1[i] * v2[j];
    }
    cout << ans;
    return 0;
}