PAT A1037 Magic Coupon

题目链接

解题思路

分为两步，先分别将两个集合从大到小排序，然后如果都为正数，就对应位置相乘并求和。然后再从小到大拍一次序，如果都为负数，就对应位置相乘并求和。最后输出结果。

代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1e5+10;
int nc[maxn],np[maxn];
int n,m;
bool cmp(int a,int b){
    return a>b;
}
bool cmp1(int a,int b){
    return a<b;
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&nc[i]);
    scanf("%d",&m);
    for(int i=0;i<n;i++) scanf("%d",&np[i]);
    sort(nc,nc+n,cmp);
    sort(np,np+m,cmp);

    int sum=0;
    for(int i=0;i<n&&i<m;i++){
        if(nc[i]>0&&np[i]>0){
            sum+=nc[i]*np[i];
        }else{
            break;
        }
    }
    sort(nc,nc+n,cmp1);
    sort(np,np+m,cmp1);

    for(int i=0;i<n&&i<m;i++){
        if(nc[i]<0&&np[i]<0){
            sum+=nc[i]*np[i];
        }else{
            break;
        }
    }
    printf("%d",sum);

    return 0;
}