排序 $O(nlogn)$
将优惠券和产品从小到大排序
将同为负数的从小到大相乘后相加
过滤掉多余的负数
将同为正数的从大到小相乘后相加
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100005;
int coupons[N], products[N];
int main(){
int n, m;
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> coupons[i];
cin >> m;
for (int i = 0; i < m; i ++ ) cin >> products[i];
sort(coupons, coupons + n);
sort(products, products + m);
int ptrC = 0, ptrP = 0;
int res = 0;
while (ptrC < n && ptrP < m && coupons[ptrC] < 0 && products[ptrP] < 0) {
res += coupons[ptrC ++] * products[ptrP ++];
}
while (ptrC < n && coupons[ptrC] <= 0) ++ ptrC;
while (ptrP < m && products[ptrP] <= 0) ++ ptrP;
int i = n - 1, j = m - 1;
while (i >= ptrC && j >= ptrP) res += coupons[i --] * products[j --];
cout << res << endl;
return 0;
}