[PAT解题报告] Magic Coupon
题目给了一个有趣的背景——在商店买东西，用不同优惠券可以把产品价值乘以一个不同系数。但是无论是系数，还是优惠券上的数都有正有负……火星上比较诡异。然后给定你产品和优惠券，问如何分配——每个产品只能用一个优惠券并且不能不用，每个优惠券只能用在一个产品上，也就是说最终要选n个产品和n个优惠券一对一搭配，让总价值和最大。
其实，这就是一个分配使得价值和最大的问题，我们知道对于a1,a2...an和b1
,b
2
...b
n如果完全分配是“同序和”最大。即a
1<=a
2<=...<=a
n并且b1
<=b
2
<=
...<=b
n时对应乘积和最大。但是，我们不一定要全部使用，如果两个乘积是负数，我们没有必要在总和里加上它们。
于是我们可以把两个数组排序，如果最大的是正数，那么我们两个数组都从最大的正数开始分配，这样乘积才最大，总和也最大。
同理，如果最小的是负数，那么我们两个数组都从最小的负数（绝对值最大）开始分配，和正数分配是对称的。符号相反的两个数，乘积是负数，不要计算在总和就好了。
注意： 结果会超int。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;
int a[100005],b[100005];
long long mul(long long x,long long y) {
return x * y;
}
int main() {
int n, m;
scanf("%d",&n);
for (int i = 0; i < n; ++i) {
scanf("%d",a + i);
}
scanf("%d",&m);
for (int i = 0; i < m; ++i) {
scanf("%d",b + i);
}
sort(a, a + n);
sort(b, b + m);
int froma = 0, fromb = 0;
long long answer = 0;
for (; (froma < n) && (fromb < m) && (a[froma] < 0) && (b[fromb] < 0); answer += mul(a[froma++], b[fromb++]))
;
for (int i = n - 1, j = m - 1; (i >= froma) && (j >= fromb) && (a[i] > 0) && (b[j] > 0); answer += mul(a[i--], b[j--]))
;
printf("%lld\n",answer);
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1037
美团开奖294人在聊
投递网易有道等公司10个岗位 >