poj2549——Sumsets

思路：枚举+二分查找。

本听说可以用hash解决，不过，感觉用排序更方便。结果一直tle,搜了报告，才知道，有降低复杂度的方法。

枚举d，用2个for()确定a,b.二分查找c。

#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 1005
int maxsum,n;
bool flag;
bool search(int left,int right,int key,int k1,int k2,int b[])
{
	int mid;
	while(left<=right)
	{
		int mid=(left+right)>>1;
		if(b[mid]==key&&mid!=k1&&mid!=k2) return true;
		if(b[mid]>key)
			right=mid-1;
		else if(b[mid]<key)left=mid+1;
	}
	return false;
}
int main()
{
	int i,a[N],j,k;
	while(scanf("%d",&n)&&n)
	{
		flag=false;
		for(i=1;i<=n;i++)
			scanf("%d",&a[i]);
		if(n<3)
			cout<<"no solution"<<endl;
		else 
		{
			maxsum=-999999999;
			sort(a+1,a+1+n);
			int b[N];
			int cnt=1;i=1;
			while(i<=n)
			{
				b[cnt++]=a[i];
				int k=i;
				while(i<=n&&a[k]==a[i])
					i++;
			}
			for(k=cnt-1;k>=1;k--)
			{
				maxsum=b[k];
				for(i=cnt-1;i>=1;i--)
				{
					if(k==i) continue;
					if(b[i]+b[0]+b[1]>maxsum) continue;
					for(j=i-1;j>=1;j--)
					{
						if(j==i||j==k) continue;
						if(search(1,j-1,maxsum-b[i]-b[j],k,i,b))
						{
							flag=true;
							goto end;
						}
					}
				}
			}
end:
			if(flag) 
				cout<<maxsum<<endl;
			else cout<<"no solution"<<endl;
		}
	}
	return 0;
}