UVA 10125 (14.3.6)

Problem C - Sumsets

Input

Output

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<stdio.h>
#include<algorithm>

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;
}

UVA 10125 (14.3.6),布布扣,bubuko.com

UVA 10125 (14.3.6)

原文：http://blog.csdn.net/qq297060023/article/details/20663051