UVa 10125 Sumsets （折半枚举&二分查找）

UVa 10125 Sumsets （折半枚举&二分查找）2014-07-25

10125 - Sumsets

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=onlinejudge&page=show_problem&problem=1066

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

52 3 5 7 1252 16 64 256 10240

Output for Sample Input

12no solution

思路见代码注释。

复杂度：O（n^2 log n）

/*0.072s*/#include<bits/stdc++.h>using namespace std;struct node{int a, b, sum; ///注意已经保证了a<b;bool operator < （const node& a） const{return sum < a.sum;}} sum[499505], tmpsum;int a[1005], tmp[4], n, c, ans, low, upp;inline bool notequal（）///判断这4个数是否互不相同{int i,j;for （i = 0; i < 3; ++i）for （j = i + 1; j < 4; ++j）if （tmp[i] == tmp[j]） return false;return true;}bool solve（）{int i,j,k;for （i = n - 1; i >= 0; --i）///从S中最大的枚举dfor （j = 0; j < n; ++j）///枚举c{if （j == i） continue;tmp[0] = a[i], tmp[1] = a[j];///a[i]是d，a[j]是ctmpsum = （node）{a[i], a[j], a[i] - a[j]};///d-clow = lower_bound（sum, sum + c, tmpsum） - sum, upp = upper_bound（sum, sum + c, tmpsum） - sum;///二分找d-cfor （k = low; k < upp; ++k）{tmp[2] = sum[k].a, tmp[3] = sum[k].b;///a和bif （notequal（））{ans = a[i];return true;}}}return false;}int main（）{int i,j;while （scanf（"%d", &n）, n）{for （i = 0; i < n; ++i） scanf（"%d", &a[i]）;if （n < 4）{puts（"no solution"）;continue;}sort（a, a + n）;c = 0;for （i = 0; i < n - 1; ++i）for （j = i + 1; j < n; ++j）sum[c++] = （node）{a[i], a[j], a[i] + a[j]};///枚举S中任意两个元素之和，并排序sort（sum, sum + c）;if （solve（）） printf（"%d
", ans）;else puts（"no solution"）;}return 0;}