PAT A1037 Magic Coupon (25分)

前言

传送门

正文

参考题解

#include<iostream>
#include<algorithm>

using namespace std;

/* 贪心问题 给出指定个数的优惠券以及产品的价值，每张优惠券上面的数字表示返回的次数， 如果每张优惠券上的数字符号与产品的价值的符号相同，则返回顾客二者的乘积作为回报； 若异号，则顾客需要支付二者的乘积给商店。现在需要求出顾客能够获得的回报的最大值是多少 */
const int N=1e5+10;
int c[N],p[N];
int n,m,res=0; 
bool cmp(int a,int b){
	return a>b;
}
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",&c[i]);
	scanf("%d",&m);
	for(int i=0;i<m;i++)scanf("%d",&p[i]);
	sort(c,c+n,cmp);
	sort(p,p+m,cmp);

	for(int i=0,j=0;i<n&&j<m;i++,j++){
		if(c[i]>=0&&p[j]>=0)res+=c[i]*p[j];
		else break;
	}
	for(int i=n-1,j=m-1;i>=0&&j>=0;i--,j--){
		if(c[i]<=0&&p[j]<=0)res+=c[i]*p[j];
		else break;
	}
	printf("%d\n",res);
	return 0;
}