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=+;
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=;
scanf("%d",&nc);
for(int i=;i<nc;i++){
scanf("%lld",&tmp);
if(tmp>=)
coupon1[c1++]=tmp;
else
coupon2[c2++]=tmp;
}
scanf("%d",&np);
for(int i=;i<np;i++){
scanf("%lld",&tmp);
if(tmp>=)
product1[p1++]=tmp;
else
product2[p2++]=tmp;
}
long long ans=;
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=;i<min1;i++){
ans+=coupon1[i]*product1[i];
}
int min2=min(c2,p2);
for(int i=;i<min2;i++){
ans+=coupon2[i]*product2[i];
}
printf("%lld\n",ans);
return ;
}
上一篇:Android Notivation的使用


下一篇:最小生成树之克鲁斯卡尔(kruskal)算法