poj2549——Sumsets

44424742

思路：枚举+二分查找。
本听说可以用hash解决，不过，感觉用排序更方便。结果一直tle,搜了报告，才知道，有降低复杂度的方法。
枚举d，用2个for()确定a,b.二分查找c。
#include<iostream>#include<string>#include<cstdio>#include<algorithm>using namespace std;#define N 1005int 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;}