Posted on 2010-08-18 16:37
acronix 阅读(488)
评论(2) 编辑 收藏 引用 所属分类:
hzshuai解题报告
题意：最小二分图匹配的变形，边的权值为两定点的乘积，求匹配中的最大乘积最小。分析：首先，两组数据中全为正时，只有大乘小才能得到最大中的最小。
明白这点后，分析两组数据的情况，都为正，都为负，一负一正，部分负部分正，考虑清楚，并想出对应的解法即可。还有就是0既可以看成负数，也可看成正数。
#include <cstdio>
#include <stdlib.h>
#include <algorithm>
using namespace std;
const long long inf = -1LL<<60;
long long a[100010],b[100010];
int xa,xb,ya,yb;
int n;
int main()
{
int i,j,k;
long long max;
while (scanf("%d",&n) != EOF)
{
max = inf;
xa = xb = ya = yb = 0;
for (i = 1; i <= n; i++)
{
scanf("%I64d",&a[i]);
if (a[i] <= 0)
ya ++;
else xa ++;
}
for (i = 1; i <= n; i++)
{
scanf("%I64d",&b[i]);
if (b[i] <= 0)
yb ++;
else xb ++;
}
sort(a+1,a+1+n);
sort(b+1,b+1+n);
//a，b全为正
if ((xa == n && xb == n) ||(xa == 0 && xb == 0))
{
for (i = 1; i <= n; i++)
if (max < a[i]*b[n-i+1])
max = a[i]*b[n-i+1];
printf("%I64d\n",max);
continue;
}
//a，b一正一负
if ((xa == n && xb == 0) || (xa == 0 && xb == n))
{
for (i = 1; i <= n; i++)
if (max < a[i]*b[i])
max = a[i]*b[i];
printf("%I64d\n",max);
continue;
}
//a全为正
if (xa == n)
{
for (i = 1; i <= xb;i++)
if (max < a[i]*b[n-i+1])
max = a[i]*b[n-i+1];
printf("%I64d\n",max);
continue;
}
//a全为负
if (xa == 0)
{
for (i = 1; i <= yb; i++)
if (max < a[n-i+1]*b[i])
max = a[n-i+1]*b[i];
printf("%I64d\n",max);
continue;
}
//b全为正
if (xb == n)
{
for (i = 1; i <= xa;i++)
if (max < b[i]*a[n-i+1])
max = b[i]*a[n-i+1];
printf("%I64d\n",max);
continue;
}
//b全为负
if (xb == 0)
{
for (i = 1; i <= ya; i++)
if (max < b[n-i+1]*a[i])
max = b[n-i+1]*a[i];
printf("%I64d\n",max);
continue;
}
//a的正==b的负
if (xa == yb)
{
for (i = 1; i <= ya; i++)
if (max < a[i]*b[yb+i])
max = a[i]*b[yb+i];
for (i = 1; i <= yb; i++)
if(max < b[i]*a[ya+i])
max = b[i]*b[yb+i];
printf("%I64d\n",max);
continue;
}
//a的正 》b的负，余下全为正
if (xa > yb)
{
for (i = ya+1,j = n - ya; i <= n-yb; i++,j--)
if (max <a[i]*b[j])
max = a[i]*b[j];
printf("%I64d\n",max);
continue;
}
//a的正小于b的负，余下全为负
if (xa < yb)
{
for (i = xb+1,j = n- xb; i <= n - xa; i++,j--)
if (max < a[i]*b[j])
max = a[i]*b[j];
printf("%I64d\n",max);
continue;
}
}
return 0;
}