poj2549——Sumsets
思路：枚举+二分查找。本听说可以用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==key&&mid!=k1&&mid!=k2) return true;if(b>key)right=mid-1;else if(b<key)left=mid+1;}return false;}int main(){int i,a,j,k;while(scanf("%d",&n)&&n){flag=false;for(i=1;i<=n;i++)scanf("%d",&a);if(n<3)cout<<"no solution"<<endl;else {maxsum=-999999999;sort(a+1,a+1+n);int b;int cnt=1;i=1;while(i<=n){b=a;int k=i;while(i<=n&&a==a)i++;}for(k=cnt-1;k>=1;k--){maxsum=b;for(i=cnt-1;i>=1;i--){if(k==i) continue;if(b+b+b>maxsum) continue;for(j=i-1;j>=1;j--){if(j==i||j==k) continue;if(search(1,j-1,maxsum-b-b,k,i,b)){flag=true;goto end;}}}}end:if(flag) cout<<maxsum<<endl;else cout<<"no solution"<<endl;}}return 0;}
页:
[1]