POJ 2549---Sumsets（二分枚举）

传送门：http://poj.org/problem?id=2549
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
5
2
3
5
7
12
5
2
16
64
256
1024
0

Sample Output
12
no solution

题意：
a, b, c, d 都是集合中的数，且满足a + b + c = d，要求出最大的d。

思路：
把a + b + c = d 转换成 a + b = d - c，先遍历每种两个数和的情况，写入结构体。在遍历每种两数相减的所有情况，用lower_bound从结构体中搜索出来，只要其中构成的数不冲突，证明这个等式成立，再用从中选择最大的ans。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <string>
#include <sstream>
#include <stack>
#include <queue>
#include <map>using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int MAX = 1e3 + 10;
int N;
ll S[MAX];
struct node
{ll s, x, y;node(){};node(ll a, ll b, ll c) {s = a;x = b;y = c;}friend bool operator < (node a, node k) {return a.s < k.s;}
}sum[MAX * MAX];
bool cmp(ll x, ll y)
{return x > y;
}
int main ()
{while(scanf("%d", &N), N) {for(int i = 0; i < N; i++) {scanf("%lld", &S[i]);}sort(S, S+N, cmp);int cnt = 0;for(int i= 0; i < N; i++) {for(int j= i+1; j < N; j++) {sum[cnt].x = S[i];sum[cnt].y = S[j];sum[cnt].s = S[i] + S[j];cnt++;}}sort(sum, sum+cnt);ll ans = -inf;for(int i= 0; i < N; i++) {for(int j= 0; j < N; j++) {if(i == j) continue;node temp (S[i]-S[j], 0, 0);int pos = lower_bound(sum, sum+cnt, temp) - sum;for(int k = pos; k < cnt && sum[k].s == S[i] - S[j]; k++) {if(sum[k].x != S[i] && sum[k].x != S[j] && sum[k].y != S[i] && sum[k].y != S[j]) {ans = max(ans, S[i]);}}}}if(ans == -inf) cout << "no solution" << endl;else cout << ans << endl;}return 0;
}