题解 P2141 【珠心算测验】

heidoudou

2018-08-07 08:20:37

Solution

这题我一开始以为是 两个数之和等于另两个数之和(不仔细看题),把问题想复杂了。 才三个数而已。用 `set`或者桶排,无非就是为了遍历两个元素的组合,快速判断这两个元素的和是否存在。如果存在,还只能记一次。 最好也要用 $O(N^2)$ 的复杂度。 换个角度:先定位第三个元素, 然后找有没有两数之和等于这个数的。不需要多余的数组、集合。 ```cpp int a[101]; int main() { int n, i; cin >> n; for (i = 0; i < n; i++) cin >> a[i]; sort(a, a + n); int count = 0; int l, r; for (i = n - 1; i >= 2; --i) { l = 0, r = i - 1; while (l < r) { if (a[l] + a[r] < a[i]) ++l; else if (a[l] + a[r] > a[i]) --r; else { count++; break; } } } cout << count; } ```