/**//* 题意:给出上面n个数,下面n个数,求完美匹配的最大边最小。边权定义为两个数相乘。可以负数 应该有点YY的 先分一下情况 同号:大*小 才能使最大那个最小 异号:小*小 才能使最大那个最小 一点贪心的思想 上面的那些正数跟下面的负数匹配 上面的那些负数跟下面的正数匹配 这样剩下来的(当然可以没有剩下),肯定是同号的,而且这些数更接近于0
现在再来看那些 正数*负数 的情况 刚才提到“小*小 才能使最大那个最小”,而且越小的话越好 所以上面那些最大的正数跟下面那些最小的负数匹配(顺序匹配,大-大,小-小) 同理,上面的那些最小的负数跟下面那些最大的正数匹配
就这样先排序,然后找出各自的0的位置 再分类一下即可 */ #include<cstdio> #include<cstring> #include<algorithm> using namespace std;
const int MAXN = 100010; const long long INF = 1LL<<62;
int A[MAXN],B[MAXN];
int main() { int n; while(~scanf("%d",&n)) { for(int i=0;i<n;i++) scanf("%d",&A[i]); for(int i=0;i<n;i++) scanf("%d",&B[i]); sort(A,A+n); sort(B,B+n); long long ans=-INF; int ka=lower_bound(A,A+n,0)-A; int kb=lower_bound(B,B+n,0)-B; int d1=min(n-ka,kb);
int a1=n-1,b1=d1-1; for(int cnt=0;cnt<d1;cnt++) { ans=max(ans,(long long)A[a1--]*B[b1--]); } int d2=min(ka,n-kb); int a2=d2-1,b2=n-1; for(int cnt=0;cnt<d2;cnt++) { ans=max(ans,(long long)A[a2--]*B[b2--]); } a1=n-1-d1,b1=d1; for(int cnt=0;cnt<n-d1-d2;cnt++) { ans=max(ans,(long long)A[a1--]*B[b1++]); } printf("%I64d\n",ans); } return 0; }
|
|
常用链接
随笔分类
Links
搜索
最新评论
|
|