POJ 2549 Sumsets（折半枚举+二分）

Sumsets

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 11946		Accepted: 3299

Description

Given S, a set of integers, find the largest d such that a + b + c = d where a, b, c, and d are distinct elements of S.

Input

Several S, each consisting of a line containing an integer 1 <= n <= 1000 indicating the number of elements in S, followed by the elements of S, one per line. Each element of S is a distinct integer between -536870912 and +536870911 inclusive. The last line of input contains 0.

Output

For each S, a single line containing d, or a single line containing "no solution".

Sample Input

Sample Output

12
no solution

Source

Waterloo local 2001.06.02

题意

给你一个公式a+b+c=d，让你在同一个集合（元素不同）内满足该条件时d的最大值，注意a b c d均不同。

思路

网上折半搜索的思路一般是将a+b+c=d拆分成 a+b=d-c

优秀的代码

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 const int inf = -600000000;
 7 int a[1001];
 8 int main()
 9 {
10     int n;
11     while (cin>>n&&n)
12     {
13         for (int i = 0; i < n; i++)
14             cin >> a[i];
15         sort(a, a + n);//从小到大
16         n--;
17         int ans = inf;
18         for (int i = n; i >= 0; i--)
19         {
20             for (int j = n; j >= 0; j--)
21             {
22                 if (i == j)
23                     continue;
24                 int sum = a[i] - a[j];
25                 for (int l = 0, r = j - 1; l<r;)//剩下用二分
26                 {
27                     if (a[l] + a[r] == sum)
28                     {
29                         if (l != i && r != i)
30                         {
31                             ans = a[i];
32                             break;
33                         }
34                     }
35                     if (a[l] + a[r]>sum)
36                         r--;
37                     else
38                         l++;
39                 }
40                 if (ans != inf)
41                     break;
42             }
43             if (ans != inf)
44                 break;
45         }
46         if (ans == inf)
47             printf("no solution
");
48         else
49             printf("%d
", ans);
50     }
51     return 0;
52 }

将a+b,c-d看成两个序列，然后二分查找。注意不要忘记去重

 1 #include<algorithm>  
 2 #include<cstdlib>  
 3 #include<cstring>  
 4 #include<string>  
 5 #include<stack>  
 6 #include<queue>  
 7 #include<iostream>  
 8 #include<cmath>  
 9 #include<map>  
10 #include<list>  
11 #include<stack>  
12 typedef long long ll;  
13 using namespace std;  
14   
15 int n;  
16 int a[1005];  
17   
18 struct node{  
19 int i,j;  
20 int val;  
21 }b[1005*1005];  
22   
23 bool cmp(node a,node b)  
24 {  
25     return a.val<b.val;  
26 }  
27   
28 bool comp1(node a,int b)  
29 {  
30     return a.val<b;  // 找到第一个val>=b的结构体元素  
31 }  
32   
33 bool comp2(node a,int b)  
34 {  
35     return a.val<=b; // 找到第一个val>b的结构体元素  
36 }  
37   
38 int main()  
39 {  
40     while(scanf("%d",&n)==1&&n)  
41     {  
42         int i,j,k,m,t;  
43         for(i=0;i<n;i++)  
44             scanf("%d",a+i);  
45         sort(a,a+n);  
46   
47         int len=0;  
48         for(i=0;i<n;i++)  
49         {  
50             for(j=i+1;j<n;j++)  
51             {  
52                 if(a[i]!=a[j])  //这里直接判断一下 不同的话再存 以后就可以减少这部判断啦  
53                 {  
54                     b[len].i=i;  
55                     b[len].j=j;  
56                     b[len].val=a[i]+a[j]; //存储题意中的 a+b  
57                     len++;  
58                 }  
59             }  
60         }  
61         sort(b,b+len,cmp);  //根据a+b的值从小到大排序  
62   
63         bool flag=false;  
64         for(i=n-1;i>=0;i--) //之前已经从小到大对sort了 所以直接从最大的开始  
65         {  
66             int d=a[i];  //我们要找的d  
67             for(j=0;j<i;j++)  
68             {  
69                 if(d!=a[j]) //d不能等于c  
70                 {  
71                     int cd=d-a[j];  //cd的值就相当于d-c  
72                     node* p1=lower_bound(b,b+len,d-a[j],comp1);  
73                     node* p2=lower_bound(b,b+len,d-a[j],comp2);//注意我写的两个函数comp, 而且都是作为lower_bound的参数  
74                     if(p2-p1!=0)  //说明存在 a+b==d-c  
75                     {  
76                         while(p1!=p2) //还要判断一下a,b,c,d是否都不相同  
77                         {  
78                             if(a[p1->i]!=a[j]&&a[p1->i]!=a[i]&&a[p1->j]!=a[j]&&a[p1->j]!=a[i])  
79                             {  
80                                 flag=true;  //符合题意 直接跳出  
81                                 break;  
82                             }  
83                             p1++;  
84                         }  
85                     }  
86                 }  
87                 if(flag)  //符合题意 直接跳出  
88                     break;  
89   
90             }  
91             if(flag)break;  //符合题意 直接跳出  
92   
93         }  
94         if(flag)printf("%d
",a[i]); //符合题意 直接输出d 也就是a[i]  
95         else printf("no solution
");  
96   
97     }  
98

View Code

 1 #include<cstdio>  
 2 #include<algorithm>  
 3 using namespace std;  
 4 typedef long long ll;  
 5 const int maxn=1000+5;  
 6 ll t[maxn],d[maxn*maxn];  
 7 struct node  
 8 {  
 9     ll sum;  
10     int use1,use2;  
11 } c[maxn*maxn];  
12 bool cmp(const node& a,const node& b)  
13 {  
14     return a.sum<b.sum;  
15 }  
16 int main()  
17 {  
18     int n;  
19     while(~scanf("%d",&n),n)  
20     {  
21         int i,j,s=0;  
22         for(i=0; i<n; i++)  
23             scanf("%lld",&t[i]);  
24         sort(t,t+n);  
25         for(i=0; i<n; i++)  
26             for(j=0; j<n; j++)  
27                 if(i!=j)  
28                 {  
29                     c[s].sum=t[i]+t[j];  
30                     c[s].use1=i;  
31                     c[s++].use2=j;  
32                 }  
33         sort(c,c+s,cmp);  
34         for(i=0; i<s; i++)  
35             d[i]=c[i].sum;  
36         ll ma=-1e17;  
37         for(i=0; i<n; i++)  
38         {  
39             for(j=n-1; j>=0; j--)  
40             {  
41                 if(i!=j&&t[j]>ma)  
42                 {  
43                     ll u=-(t[i]-t[j]);  
44                     int id1=lower_bound(d,d+s,u)-d;  
45                     int id2=upper_bound(d,d+s,u)-d-1;  
46                     for(int k=id1;k<id2;k++)  
47                     {  
48                         int a=c[k].use1,b=c[k].use2;  
49                         if(a!=i&&a!=j&&b!=i&&b!=j)  
50                         {  
51                             ma=t[j];break;  
52                         }  
53                     }  
54                 }  
55             }  
56         }  
57         if(ma!=-1e17)printf("%lld
",ma);  
58         else printf("no solution
");  
59     }  
60     return 0;  
61 }

View Code