PAT甲级——A1037 Magic Coupon

The magic shop in Mars is offering some magic coupons. Each coupon has an integer

For example, given a set of coupons { 1 2 4 $- }, and a set of product values { 7 6 - - } (in Mars dollars M$) where a negative value corresponds to a bonus product. You can apply coupon 3 (with$

Each coupon and each product may be selected at most once. Your task is to get as much money back as possible.

Input Specification:

Each input file contains one test case. For each case, the first line contains the number of coupons

Output Specification:

For each test case, simply print in a line the maximum amount of money you can get back.

Sample Input:

Sample Output:

 1 #include <iostream>
 2 #include <vector>
 3 #include <string>
 4 #include <algorithm>
 5 using namespace std;
 6 //牛客这道题涉及数相乘会int溢出，而PAT没有，所以pat使用int类型就可以，而牛客需要使用longlong型
 7 long long Nc, Np, p = 0, q = 0, a, res = 0;
 8 int main()
 9 {
10     cin >> Nc;
11     vector<long>Vc, Vp;
12     for (int i = 0; i < Nc; ++i)
13     {
14         cin >> a;
15         Vc.push_back(a);
16     }
17     cin >> Np;
18     for (int i = 0; i < Np; ++i)
19     {
20         cin >> a;
21         Vp.push_back(a);
22     }
23     sort(Vc.begin(), Vc.end(), [](long long u, long long v) {return u < v; });
24     sort(Vp.begin(), Vp.end(), [](long long u, long long v) {return u < v; });
25     while (p < Nc&&q < Np&&Vc[p] < 0 && Vp[q] < 0)//先负数相乘
26     {
27         res += Vc[p] * Vp[q];
28         ++p;
29         ++q;
30     }
31     p = Nc - 1;
32     q = Np - 1;
33     while (p >= 0 & q >= 0 && Vc[p] > 0 && Vp[q] > 0)//正数从后开始乘
34     {
35         res += Vc[p] * Vp[q];
36         --p;
37         --q;
38     }
39     cout << res << endl;
40     return 0;
41 }