HDU 2578 Dating with girls(1)

题目链接~~>

 做题感悟：在搜二分题时搜到它，不小心看到一个标题（二分+排序），以后不能这样找题目做了，知道方法就没意思了，其实这题很水。

 解题思路：( 1 ).可以二分 + 排序（去重，也可以不去重），因为没去重错了几次 ; ( 2 ). map 可以轻松解决（时间比较长）。

代码（二分+排序）：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      int g[100005],g1[100005] ;
     
    
   

    

     

    
    

     

      int binary_search(int x,int y,int n) // 二分
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int mid ;
     
    
   

    

     

    
    

     
 while(x<y)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       mid=x+(y-x)/2 ;
     
    
   

    

     

    
    

     
 if(g1[mid]==n)
     
    
   

    

     

    
    

     
 return mid ;
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       g1[mid] > n ? y=mid : x=mid+1 ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return -1 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int T,i,k,n ;
     
    
   

    

     

    
    

     
 scanf("%d",&T) ;
     
    
   

    

     

    
    

     
 while(T--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d%d",&n,&k) ;
     
    
   

    

     

    
    

     
 for(i=0 ;i<n ;i++)
     
    
   

    

     

    
    

     
 scanf("%d",&g[i]) ;
     
    
   

    

     

    
    

     

       sort(g,g+n) ;
     
    
   

    

     

    
    

     
 int r=1 ;  g1[0]=g[0]  ;
     
    
   

    

     

    
    

     
 for(i=1 ;i<n ;i++) // 去重
     
    
   

    

     

    
    

     
 if(g[i]!=g[i-1])
     
    
   

    

     

    
    

     

       g1[r++]=g[i] ;
     
    
   

    

     

    
    

     
 int num=0 ;
     
    
   

    

     

    
    

     
 for(i=0 ;i<r ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int a=k-g1[i] ;
     
    
   

    

     

    
    

     
 if(a<g1[i]) continue ;
     
    
   

    

     

    
    

     
 if(g1[i]*2==k)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       num++ ;continue ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 int mx=binary_search(0,r,a) ;
     
    
   

    

     

    
    

     
 if(mx!=-1)
     
    
   

    

     

    
    

     

       num+=2 ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 printf("%d\n",num) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

代码（map）：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      map<int,int>m ;
     
    
   

    

     

    
    

     

      int g[100005] ;
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int T,n,k ;
     
    
   

    

     

    
    

     
 scanf("%d",&T) ;
     
    
   

    

     

    
    

     
 while(T--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d%d",&n,&k) ;
     
    
   

    

     

    
    

     

       m.clear() ;  // 一定要清空
     
    
   

    

     

    
    

     
 int r=0,x ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<n ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d",&x) ;
     
    
   

    

     

    
    

     
 if(!m[x])
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       g[r++]=x ; m[x]=1 ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 int num=0 ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<r ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(m[k-g[i]]&&k>=g[i])
     
    
   

    

     

    
    

     

       num+=1 ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 printf("%d\n",num) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/17528533