
 /**//*
題意:給出上面n個(gè)數(shù),下面n個(gè)數(shù),求完美匹配的最大邊最小。邊權(quán)定義為兩個(gè)數(shù)相乘。可以負(fù)數(shù)
應(yīng)該有點(diǎn)YY的
先分一下情況
同號(hào):大*小 才能使最大那個(gè)最小
異號(hào):小*小 才能使最大那個(gè)最小
一點(diǎn)貪心的思想
上面的那些正數(shù)跟下面的負(fù)數(shù)匹配
上面的那些負(fù)數(shù)跟下面的正數(shù)匹配
這樣剩下來的(當(dāng)然可以沒有剩下),肯定是同號(hào)的,而且這些數(shù)更接近于0

現(xiàn)在再來看那些 正數(shù)*負(fù)數(shù) 的情況
剛才提到“小*小 才能使最大那個(gè)最小”,而且越小的話越好
所以上面那些最大的正數(shù)跟下面那些最小的負(fù)數(shù)匹配(順序匹配,大-大,小-小)
同理,上面的那些最小的負(fù)數(shù)跟下面那些最大的正數(shù)匹配

就這樣先排序,然后找出各自的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
搜索
最新評(píng)論

|
|