关于算法-数据结构:PAT甲级1037-Magic-Coupon

38次阅读

共计 830 个字符,预计需要花费 3 分钟才能阅读完成。

题目粗心:

给出两个汇合,从这两个汇合中别离选取雷同数量的元素进行一对一相乘,问能失去的最大乘积之和是多少。

算法思路:

很直观的感触就是将 2 个汇合中负数大的顺次相乘,正数小的顺次相乘而后再相加。对这 2 个汇合都从小到大进行排序,那么从左往右将雷同地位的正数进行相乘,而后从右往左将雷同地位的负数进行相乘,并且将其问题累加就是最终后果。

留神点:

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

提交后果:

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