1037 Magic Coupon (25 分)

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:

43

这题只能说是简单贪心了

 1 #include <bits/stdc++.h>
 2 #define N 100005
 3 using namespace std;
 4 int n,m;
 5 int an[N], bn[N];
 6 
 7 int main(){
 8     cin >> n;
 9     for(int i = 0; i < n; i++){
10         cin >> an[i];
11     }
12     sort(an,an+n);
13     cin >> m;
14     for(int i = 0; i < m; i++){
15         cin >> bn[i];
16     }
17     sort(bn,bn+m);
18     int sum = 0;
19     int i = 0, ii = n-1;
20     int j = 0, jj = m-1;
21     while(i <= ii && j <= jj){
22         bool flag = true;
23         if(an[i]*bn[j] > an[ii]*bn[jj]){
24             if(an[i]*bn[j]>0){
25                 sum += an[i]*bn[j];
26                 i++;
27                 j++;
28                 flag = false;
29             }
30         }else{
31             if(an[ii]*bn[jj] > 0){
32                 sum += an[ii]*bn[jj];
33                 ii--;
34                 jj--;
35                 flag = false;
36             }
37         }
38         if(flag)
39             break;
40     }
41     cout << sum << endl;
42     return 0;
43 }