//
// main.cpp
// PAT_1037. Magic Coupon
//
// Created by wjq on 17/5/7.
// Copyright © 2017年 wjq. All rights reserved.
//
#include <iostream>
#include <algorithm>
using namespace std;
long long int NC[100005],NP[100005],temp=0,sum=0;
int numOfNC=0,numOfNP=0;
int main(int argc, const char * argv[])
{
cin>>numOfNC;
for(int i=0;i<numOfNC;i++)
cin>>NC[i];
cin>>numOfNP;
for(int i=0;i<numOfNP;i++)
cin>>NP[i];
sort(NC,NC+numOfNC);
sort(NP,NP+numOfNP);
if(numOfNC<numOfNP)
{
for(int i=0;i<numOfNC;i++)
{
if(NC[i]>=0)
break;
temp=NC[i]*NP[i];
if(temp<0)
continue;
sum+=temp;
}
for(int i=numOfNC-1;i>=0;i--)
{
if(NC[i]<0)
break;
temp=NC[i]*NP[numOfNP-(numOfNC-i)];
if(temp<0)
continue;
sum+=temp;
}
}
else if(numOfNC>numOfNP)
{
for(int i=0;i<numOfNP;i++)
{
if(NP[i]>=0)
break;
temp=NC[i]*NP[i];
if(temp<0)
continue;
sum+=temp;
}
for(int i=numOfNP-1;i>=0;i--)
{
if(NP[i]<0)
break;
temp=NC[numOfNC-(numOfNP-i)]*NP[i];
if(temp<0)
continue;
sum+=temp;
}
}
cout<<sum<<endl;
return 0;
}
简单题,但是有点麻烦,因为NP和NC的的大小需要讨论.
思路很简单,就是对NP和NC进行排序(得到两个从小到大增大的序列),然后对两个序列从左边匹配负数的乘法,从右边匹配正数的乘法.遇到相乘是负数的过滤掉.
