[NOIP 2014 普及组 T1]珠心算测验
看n的值不大，所以估算一下枚举的时间复杂度。大概是O(n^3)。n最大是100，暴力破解应该能过。初学者值得尝试一下。。
一定要仔细读题。尤其是“其中有多少个数，恰好等于集合中另外两个（不同的）数之和”这句话。千万不能理解成为：“两个数的和是集合中的另外一个数”。
这两句话有很大的不同。比如，下面的例子：
5
1 2 3 4 5
这组测试数据，有
3 = 1 + 2 ?
4 = 1 + 3 ?
5 = 1 + 4 ?
5 = 2 + 3
后面两个数重复了，所以对于前面那句话结果是3个，对于后面那句话结果是4个。
#include <bits/stdc++.h>
using namespace std;
int x[110];
int main()
{
int n, cnt = 0;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> x[i];
sort(x + 1, x + 1 + n);
for (int k = 3; k <= n; k++)
{
bool ok = false;
for (int i = 1; i <= k - 2; i++)
{
for (int j = i + 1; j <= k - 1; j++)
{
if (x[k] == x[i] + x[j])
{
ok = true;
cnt++;
break;
}
}
if (ok)
break;
}
}
cout << cnt << endl;
return 0;
}再考虑优化的问题。因为数组已经排序过。那么对于公式C = A+B，可以枚举C和A。用二分答案算法搜索数组中是否存在B。效率应该能有略微提高。
#include <bits/stdc++.h>
using namespace std;
int x[110];
int main()
{
int n, cnt = 0;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> x[i];
sort(x + 1, x + 1 + n);
//x[k] = x[i] + B
for (int k = 3; k <= n; k++)
{
for (int i = 1; i <= k - 2; i++)
{
int B = x[k] - x[i];
int *p = lower_bound(x + 1 + i, x + 1 + k, B);
if (*p == B)
{
cnt++;
break;
}
}
}
cout << cnt << endl;
return 0;
}