空位与数(game)
贪心即可,因为正正得正,负负也得正,所以将两个数组分别按照正负性分开,然后让正数里面大的配上大的,负数里面绝对值大的配上绝对值大的,这样可以让正积总和尽量大。剩下不足的(必须要一正一负相乘的)让绝对值大的配绝对值小的,这样可以让负积总和尽量小。
#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e5+5;
int n,m,a[N],b[N];
int a1n,a2n,b1n,b2n;
long long a1[N],a2[N],b1[N],b2[N];
long long ans=0;bool cmp(int x,int y){return x>y;}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&a[i]);if(a[i]>=0) a1[++a1n]=a[i];else a2[++a2n]=a[i];}sort(a1+1,a1+a1n+1,cmp);sort(a2+1,a2+a2n+1);for(int i=1;i<=m;i++){scanf("%d",&b[i]);if(b[i]>=0) b1[++b1n]=b[i];else b2[++b2n]=b[i];}sort(b1+1,b1+b1n+1,cmp);sort(b2+1,b2+b2n+1);for(int i=1;i<=a1n;i++){if(i<=b1n) ans+=a1[i]*b1[i];else ans+=a1[i]*b2[b2n-(i-b1n)+1];}for(int i=1;i<=a2n;i++){if(i<=b2n) ans+=a2[i]*b2[i];else ans+=a2[i]*b1[b1n-(i-b2n)+1];}printf("%lld\n",ans);return 0;
}