题目

Describe

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
显然 O(n4) 肯定超时

保证等号两侧的时间复杂度相同
将 c 移位
得到 a + b = d - c

1000 的数据量 O(n2) 的复杂度可以接受
先算出来所有的 a + b
然后枚举所有的 d - c
二分查找找到满足题意的

细节需要注意
存在负数,需要考虑到这一点

代码

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <functional>

using namespace std;

const int maxn = 1005;

struct Node {
    int a,b;
    int sum;
    bool operator < (const int &rhs)const {
        return sum < rhs;
    }
    bool operator < (const Node &rhs)const {
        return sum < rhs.sum;
    }
};

int n;
int a[maxn];
Node sum[maxn*maxn];

bool Do() {
    cin >> n;
    if(n == 0)
        return false;
    int pos = 0;
    for(int i = 0;i < n;i++) {
        cin >> a[i];
    }
    sort(a,a + n);
    for(int i = 0;i < n;i++)
        for(int j = 0;j < i;j++) {
            sum[pos].a = j;
            sum[pos].b = i;
            sum[pos++].sum = a[i] + a[j];
        }

    sort(sum,sum + pos);
    bool flag = true;
    int ans;

    for(int i = n - 1;i >= 0 && flag;i--)
        for(int j = n - 1;j >= 0 && flag;j--) {
            int minute = a[i] - a[j];
            int it = lower_bound(sum,sum + pos,minute) - sum;
            for(it;it < pos;it++) {
                if(sum[it].sum != minute)
                    break;
                if(sum[it].b < j && i != j) {
                    ans = a[i];
                    flag = false;
                    break;
                }
            }
        }

    if(flag)
        cout << "no solution" << endl;
    else
        cout << ans << endl;


    return true;
}

int main() {
    while(Do());
    return 0;
}