问题 B: 赌徒
时间限制: 1 Sec 内存限制: 32 MB
提交: 30 解决: 8
[提交][状态][讨论版]
题目描述
有n个赌徒打算赌一局。规则是：
每人下一个赌注，赌注为非负整数，且任意两个赌注都不相同。胜者为赌注恰好是其余任意三个人的赌注之和的那个人。如果有多个胜者，我们取赌注最大的那个为最终胜者。
例如，A，B，C，D，E分别下赌注为2、3、5、7、12，最终胜者是E，因为12=2+3+7。
输入
输入包含多组测试数据。每组首先输入一个整数n（1<=n<=1000），表示赌徒的个数。
接下来n行每行输入一个非负整数b（0<=b<32768），表示每个赌徒下的赌注。
当n=0时，输入结束。
输出
对于每组输入，输出最终胜者的赌注，如果没有胜者，则输出no solution。
样例输入
5
2
3
5
7
12
5
2
16
64
256
1024
0
样例输出
12
no solution
题意概括：
查找数列中是否有一个数等于其他三个数之和，如果有输出，若有多个则输出最大的。
解题分析：
这道题我是用暴力查找的，但是要稍微优化下时间，不然会超时。我是将数列按升序排序，然后从最大的一端开始查找，这样一旦找到一个符合条件的就一定是最大的不管还有没有其他的值，找到后直接输出就可以了。
测试样例：
6
6
3
2
4
2
5
3
0
3
6
4
6
99
0
33
0
测试样例输出：
6
no solution
no solution
代码：
1 #include<stdio.h> 2 #include<algorithm> 3 4 using namespace std; 5 6 int main() 7 { 8 int n, i, j, flag, k; 9 int a[1005]; 10 while(scanf("%d", &n), n != 0){ 11 flag = 0; 12 for(i = 0; i < n; i++) 13 scanf("%d", &a[i]); 14 sort(a, a+n); 15 for(i = n-1; i >= 2; i--){ 16 for(j = i-1; j >= 1; j--){ 17 for(k = j-1; k >= 0; k--){ 18 if(a[i]-a[j] == a[k]){ 19 printf("%d ", a[i]); 20 flag = 1; 21 break; 22 } 23 } 24 if(flag) 25 break; 26 } 27 if(flag) 28 break; 29 } 30 if(!flag) 31 printf("no solution "); 32 } 33 return 0; 34 }