ZOJ 1101 Gamblers 二分

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=101

让你在一堆互不相同的数中查找是否有a=b+c+d，若有不同的解，则输出最大的。

思路：

排序后二分，从大到小枚举。设sum=a[index]-a[i]-a[j]，然后查找sum是否在数组中存在即可。

二分要写对，然后i==j || index==j || index==i等于的情况要去除。

还有用goto从内重循环直接跳出，而不是用个标记一次次判断，简洁而优雅。

#include<cstdio>

#include<algorithm>

using namespace std;

const int MAXN=1024;

int a[MAXN];

int n;

int search(int target)

{

	int L=0,R=n-1;

	while(L<R)

	{

		int mid=((L+R)>>1);

		if(a[mid]==target)

			return mid;

		else if(a[mid] < target)

			L=mid+1;

		else

			R=mid;

	}

	return -1;

}

int main()

{

	while(~scanf("%d",&n),n)

	{

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

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

		sort(a,a+n);

		int index;

		for(index=n-1;index>=0;index--)

		{

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

			{

				if( i == index ) continue;

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

				{

					if(i==j ||j==index)

						continue;

					int sum=a[index]-a[i]-a[j];

					int id=search(sum);

					if(id!=-1 && id!=i && id !=j && id != index)

					{

						printf("%d\n",a[index]);

						goto end;

					}

				}

			}

		}

		printf("no solution\n");

	end:;

	}

	return 0;

}

巴特西

ZOJ 1101 Gamblers 二分

最新文章

热门文章