1037 Magic Coupon（贪心，排序）

我就是我 2024-04-08 12:44 71阅读 0赞

## 1037 Magic Coupon（贪心，排序） ##

### 0、题目 ###

The magic shop in Mars is offering some magic coupons. Each coupon has an integer *N* printed on it, meaning that when you use this coupon with a product, you may get *N* times the value of that product back! What is more, the shop also offers some bonus product for free. However, if you apply a coupon with a positive *N* to this bonus product, you will have to pay the shop *N* times the value of the bonus product… but hey, magically, they have some coupons with negative *N*’s!

For example, given a set of coupons \{ 1 2 4 −1 \}, and a set of product values \{ 7 6 −2 −3 \} (in Mars dollars M$) where a negative value corresponds to a bonus product. You can apply coupon 3 (with *N* being 4) to product 1 (with value M$7) to get M$28 back; coupon 2 to product 2 to get M$12 back; and coupon 4 to product 4 to get M$3 back. On the other hand, if you apply coupon 3 to product 4, you will have to pay M$12 to the shop.

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 *N\*\*C*, followed by a line with *N\*\*C* coupon integers. Then the next line contains the number of products *N\*\*P*, followed by a line with *N\*\*P* product values. Here 1≤*N\*\*C*,*N\*\*P*≤105, and it is guaranteed that all the numbers will not exceed 230.

#### Output Specification: ####

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

#### Sample Input: ####

4
    1 2 4 -1
    4
    7 6 -2 -3

#### Sample Output: ####

### 1、大致题意 ###

给出两个数字序列，从这两个序列中分别选取相同数量的元素进行一对一相乘，问能得到的乘积之和最大为多少

### 2、基本思路 ###

把这两个序列在存储时，将正数和负数分开，并将正数从大到小排序，负数从小到大排序。将前面都是负数的数相乘求和，然后将后面都是正数的数相乘求和。

### 3、AC代码 ###

#include<iostream>
    #include<algorithm>
    #include<vector>
    using namespace std;
    int n,m,tmp;
    vector<int>az,af,bz,bf;
    
    int main() {
        
    	cin>>m;
    	for(int i=0; i<m; i++) {
        
    		cin>>tmp;
    		if(tmp>0) {
        
    			az.push_back(tmp);
    		} else {
        
    			af.push_back(tmp);
    		}
    	}
    	sort(az.begin(),az.end(),greater<int>());
    	sort(af.begin(),af.end(),less<int>());
    	cin>>n;
    	for(int i=0; i<n; i++) {
        
    		cin>>tmp;
    		if(tmp>0) {
        
    			bz.push_back(tmp);
    		} else {
        
    			bf.push_back(tmp);
    		}
    	}
    	sort(bz.begin(),bz.end(),greater<int>());
    	sort(bf.begin(),bf.end(),less<int>());
    	int ans=0;
    	int size=min(az.size(),bz.size());
    	for(int i=0; i<size; i++) {
        
    		ans+=az[i]*bz[i];
    	}
    	size=min(af.size(),bf.size());
    	for(int i=0; i<size; i++) {
        
    		ans+=af[i]*bf[i];
    	}
    	cout<<ans;
    	return 0;
    }

![在这里插入图片描述][c1b9dec12e6b49cbb0baa98d945cbbee.png]

[c1b9dec12e6b49cbb0baa98d945cbbee.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/05450ffab4e545189d296bc0fe994fa9.png