PAT 甲级 1037 Magic Coupon (25 分) （较简单,贪心）

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:

题意：

给出两个集合，从这两个集合里面选出数量相同的元素进行一对一相乘，求能够得到的最大乘积之和。

题解：

对每个集合，将正数和负数分开考虑，将每个集合里的整数从大到小排序；将每个集合里的负数从小到大排序，然后同位置的正数与正数相乘，负数与负数相乘。

注意点：

输入为0的不要管，直接忽略，否则测试点1过不去

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll na[100005];
ll pa[100005];
ll nb[100005];
ll pb[100005];
int kna=0,kpa=0,knb=0,kpb=0;
int n1,n2;
bool cmp(ll x, ll y){
    return x>y;
}
ll s=0;
int main(){
    cin>>n1;
    ll x;
    for(int i=1;i<=n1;i++){
        cin>>x;
        if(x>0){
            pa[++kpa]=x;
        }else if(x<0){//=0的不要管 
            na[++kna]=x;
        }
    }
    cin>>n2;
    for(int i=1;i<=n2;i++){
        cin>>x;
        if(x>0){
            pb[++kpb]=x;
        }else if(x<0){//=0的不要管 
            nb[++knb]=x;
        }
    }
    sort(pa+1,pa+1+kpa,cmp);
    sort(pb+1,pb+1+kpb,cmp);
    sort(na+1,na+1+kna);
    sort(nb+1,nb+1+knb);
    int min_l=min(kpa,kpb);
    for(int i=1;i<=min_l;i++){
        s+=pa[i]*pb[i];
    }
    min_l=min(kna,knb);
    for(int i=1;i<=min_l;i++){
        s+=na[i]*nb[i];
    }
    cout<<s<<endl;
    return 0;
}