做法:从左往右枚举前两个数的和sum,剩余的数二分找-sum是否存在。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#include <bits/stdc++.h> using namespace std; struct Node { int a, b, c; }temp; int main() { int n; int a[1010]; scanf ( "%d" , &n); for ( int i = 0; i < n; i++) scanf ( "%d" , &a[i]); sort(a, a+n); vector<Node>ans; for ( int i = 0; i < n-2; i++) { for ( int j = i+1; j < n-1; j++) { int sum = a[i] + a[j]; int pos = lower_bound(a+j+1, a+n, -sum) - a; if (pos >= n || a[pos] != -sum) continue ; // cout << i << ' ' << j <<' ' << pos << endl; temp.a = a[i]; temp.b = a[j]; temp.c = a[pos]; ans.push_back(temp); } } if (ans.size() == 0) { puts ( "No Solution" ); return 0; } for ( int i = 0; i < ans.size(); i++) { cout << ans[i].a << ' ' << ans[i].b << ' ' << ans[i].c << endl; } } |
感觉比第一题还简单,是因为数据太弱? 三个for枚举前三个数和sum, 二分剩余的数找-sum。
测试数据三个数sum居然不会爆int
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include <bits/stdc++.h> using namespace std; int main() { int n; int a[1010]; scanf ( "%d" , &n); for ( int i = 0; i < n; i++) scanf ( "%d" , &a[i]); sort(a, a+n); for ( int i = 0; i < n-3; i++) { for ( int j = i+1; j < n-2; j++) { for ( int k = j+1; k < n-1; k++) { int sum = a[i] + a[j]; sum += a[k]; int pos = lower_bound(a+k+1, a+n, -sum) - a; if (pos >= n || a[pos] != -sum) continue ; puts ( "Yes" ); return 0; } } } puts ( "No" ); } |