UVA 10125 (14.3.6)

Problem C - Sumsets

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 <= 1000indicating 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

Output for Sample Input

12
no solution

題意：S個數，從中選出四個，要符合a+b+c = d

思路：

首先，如果暴力枚舉，那麼有四層循環，看看數據大小，必超時～

那我們換思路，大體上，S個數先存在數組排序排一下，再利用四個數的相互制約的關系來解題，減少不必要的嘗試

排序簡單，sort一下即可，制約關系就要找了，之前我們排序過，那第一個數是最小的，不可能是d吧?

So，我們明白了d是和，大於a b c中的任何一個數，那麼我們就從數組中的最後一個開始枚舉好了

接下來，我們假設a < b < c 那麼我們得出 d - c = a + b對不?

這樣就清晰了, 我們從數組後端從大到小枚舉c 和 d, 並滿足c < d; 然後從數組前端從小到大枚舉a 和 b, 並滿足a < b

剩下的還有一步對於a和b的特殊處理, 交給你們自己代碼意會~

AC代碼:

#include
#include

using namespace std;

int num[1005];

int main() {
    int s;
    while(scanf("%d", &s) != EOF) {
        if(s == 0)
            break;
        for(int i = 0; i < s; i++)
            scanf("%d", &num[i]);
        sort(num, num+s);
        
        int a, b, c, d;
        int judge = 0;
        for(d = s-1; d >= 0; d--) {
            int ans;
            for(c = s-1; c > 1; c--) {
                if(c != d)
                    ans = num[d] - num[c];
                for(a = 0, b = c-1; a < b;) {
                    if(num[a] + num[b] == ans) {
                        judge = 1;
                        break;
                    }
                    else if(num[a] + num[b] < ans)
                        a++;
                    else
                        b--;
                }
                if(judge)
                    break;
            }
            if(judge)
                break;
        }
        if(judge)
            printf("%d\n", num[d]);
        else
            printf("no solution\n");
    }
    return 0;
}