• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

PAT_甲级_1037 Magic Coupon

互联网 diligentman 2周前 (10-14) 10次浏览

题目大意:

给出两个集合,从这两个集合中分别选取相同数量的元素进行一对一相乘,问能得到的最大乘积之和是多少。

算法思路:

很直观的感受就是将2个集合中正数大的依次相乘,负数小的依次相乘然后再相加。对这2个集合都从小到大进行排序,那么从左往右将相同位置的负数进行相乘,然后从右往左将相同位置的正数进行相乘,并且将其成绩累加就是最终结果。

注意点:

1、不要通过乘积大于0来判断2个数字都是负数。

提交结果:

PAT_甲级_1037 Magic Coupon

AC代码:

#include <cstdio>
#include <algorithm>

using namespace std;

int main(){
    int NC;// coupon的数目
    scanf("%d",&NC);
    int coupons[NC];
    for (int i = 0; i < NC; ++i) {
        scanf("%d",&coupons[i]);
    }
    int NP;// product的数目
    scanf("%d",&NP);
    int products[NP];
    for (int j = 0; j < NP; ++j) {
        scanf("%d",&products[j]);
    }
    sort(coupons,coupons+NC);
    sort(products,products+NP);
    int len = NC>NP?NP:NC;
    int ans = 0;
    //首先从左到右将负数的coupons和product相乘
    for (int k = 0; k < len; ++k) {
        if(coupons[k]<0&&products[k]<0){
            ans += coupons[k]*products[k];
        } else{
            break;
        }
    }
    // 然后从右往左将正数的coupons和product相乘
    for (int i=NC-1,j=NP-1;i>=0&&j>=0;--i,--j) {
        if(coupons[i]>0&&products[j]>0){
            ans += coupons[i]*products[j];
        } else{
            break;
        }
    }
    printf("%d",ans);
    return 0;
}

喜欢 (0)