首页 > 代码库 > PAT甲题题解-1037. Magic Coupon (25)-贪心,水
PAT甲题题解-1037. Magic Coupon (25)-贪心,水
题目说了那么多,就是给你两个序列,分别选取元素进行一对一相乘,求得到的最大乘积。
将两个序列的正和负数分开,排个序,然后分别将正1和正2前面的相乘,负1和负2前面的相乘,累加和即可。
#include <iostream> #include <cstdio> #include <algorithm> #include <string.h> #include <cmath> #include <vector> using namespace std; const int maxn=100000+5; int coupon1[maxn]; int c1; int coupon2[maxn]; int c2; int product1[maxn]; int product2[maxn]; int p1,p2; bool cmp(int a,int b){ return a>b; } int main() { int nc,np; long long tmp; c1=c2=p1=p2=0; scanf("%d",&nc); for(int i=0;i<nc;i++){ scanf("%lld",&tmp); if(tmp>=0) coupon1[c1++]=tmp; else coupon2[c2++]=tmp; } scanf("%d",&np); for(int i=0;i<np;i++){ scanf("%lld",&tmp); if(tmp>=0) product1[p1++]=tmp; else product2[p2++]=tmp; } long long ans=0; sort(coupon1,coupon1+c1,cmp); sort(product1,product1+p1,cmp); sort(coupon2,coupon2+c2); sort(product2,product2+p2); int min1=min(c1,p1); for(int i=0;i<min1;i++){ ans+=coupon1[i]*product1[i]; } int min2=min(c2,p2); for(int i=0;i<min2;i++){ ans+=coupon2[i]*product2[i]; } printf("%lld\n",ans); return 0; }
PAT甲题题解-1037. Magic Coupon (25)-贪心,水
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。