1.题意
https://pintia.cn/problem-sets/994805342720868352/problems/994805451374313472
从两个集合中分别取出相同个数的元素进行一对一相乘，求乘积之和的MAX。
2.贪心策略
可以直观想到贪心策略：要max，就用绝对值大的负数两两相乘，大的正数两两相乘，最后累加乘积；而在具体实现中，不用单独拆开正负数——直接分别对2个集合sort排序后，分别用两个while，即第一个while是对两个集合同时从左到右进行遍历，两两乘积后累加。第二个while是对两个集合同时从右到左进行遍历，即对2个大整数进行两两乘积后累加。
在第二个while之前，要分别取位置n-1和m-1，而非取两个集合的最小值min{n-1，m-1}。
3.注意
（1）sort默认是从小到大排序，用头文件<algorithm>；
（2）while判断条件不能是coupon[i]*product[i]>0（处理负数时）或者coupon[i]*coupon[j]>0（处理正数时）作为判断条件——因为比如两个集合正数个数相同、负数个数相同时，第一个while就累加完了所有正*正和负*负的所有情况了，而第二个while再累加也就多计算了。
（3）虽然原题说“所有的数字都不超过2^30”，即包括乘积之和不超过2^30，以防万一可以令ans变量的数据类型为long long（以免越界）。
（4）while判断条件不用纳入0情况，因为0乘任何数都是0，即对乘积之和结果没影响。
4.代码
#include<stdio.h> #include<algorithm> using namespace std; //对两个集合从小到大排序,大负*大负 大正*大正 const int maxn=100010; int coupon[maxn],product[maxn]; int main(){ int n,m; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&coupon[i]); } scanf("%d",&m); for(int i=0;i<m;i++){ scanf("%d",&product[i]); } sort(coupon , coupon+n); //从小到大排序 sort(product , product+m); int i=0,j,ans=0; //ans存放乘积之和 while(i<n && i<m && coupon[i] <0 && product[i] <0){ ans +=coupon[i] * product[i]; //当前位置均小于0时，累加乘积 i++; } i=n-1; j=m-1; while(i>=0 && j>=0 && coupon[i]>0 && product[j] >0){ ans +=coupon[i]*product[j]; //当前位置均大于0时，累加乘积 i--,j--; } printf("%d\n",ans); system("pause"); return 0; }
