posts - 64, comments - 4, trackbacks - 0, articles - 0

hdu_3512

Posted on 2010-08-18 16:37 acronix 阅读(429) 评论(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
;
}

Feedback

# re: hdu_3512  回复  更多评论   

2010-08-20 19:57 by TPP
TPP留下脚印

# re: hdu_3512  回复  更多评论   

2010-08-21 14:10 by acronix

欢迎欢迎!!!

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理