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