ACM-简单题之Dating with girls1——hdu2578

5

一道水题（我WA好多次。。。）

题意就是给你T个数，查看 两个数相加等于k的个数 。

明显的查找题目，之前做省赛有一道感觉类似，于是直觉般的想用排序+二分查找来搞定这道题。

以第一个sample为例，k为4，所以1+3,和2+2，还有3+1。

a+b和b+a是可以算作两种的，但是有一点要注意，人家可能给你多个1和一个3，这样也是只能算两种。

为什么我WA好多次呢？

第一次是多个1，一个3没想到，WA一次，自己看了遍题意，改回来了。

后面实在不知道自己哪错。。

于是，看人家代码。

差别在于，我在输入的时候做了一个判断，输入的T个数中，有大于等于K的，一律舍弃，不存入数组。

我把这个改回来，无论啥样全都输入进数组，结果就A了。。

我现在也不大懂为什么不能舍弃掉那些。。望各位给予解答。。Thank U~

/*
Author：Tree
From： http://blog.csdn.net/lttree
Dating with girls1 
hdu 2578
排序+二分查找
*/

#include <iostream>
#include <algorithm>

using namespace std;
int arr[100001];

// 二分查找，返回是否查找到。
bool binary_search( int v,int len )
{
	int l,h,m;
	l=0,h=len-1;
	while( l<=h )
	{
		m=(l+h)/2;
		if(arr[m]==v)	return 1;
		else if( arr[m]>v )	h=m-1;
		else	l=m+1;
	}
	return 0;
}

int main()
{
	int i,t,k,test,temp,sum;
	cin>>test;
	while(test--)
	{
		cin>>t>>k;
		for(i=0;i<t;++i)
			cin>>arr[i];	
		sort(arr,arr+t);

		sum=0;
		for(i=0;i<t;++i)
		{
			if( binary_search(k-arr[i],t) )
			{
				++sum;
				// 如果查找的是两个相同的数，那么只能算一次
				if( i!=0 && arr[i-1]==arr[i])
					--sum;
			}
		}
		cout<<sum<<endl;
	}
	return 0;
}

ACM-简单题之Dating with girls1——hdu2578,布布扣,bubuko.com

ACM-简单题之Dating with girls1——hdu2578

原文：http://blog.csdn.net/lttree/article/details/24474527