题目描述:
给出 n 个不同的正整数 a[1] ~ a[n],它们的值在 1~1000000 之间。再给定一个整数 x,编程计算这样的数对个数(a[i],a[j]),1≤i<j≤n 并且 a[i]+a[j]=x。
输入
第 1 行 1 个正整数 n,1≤n≤100000。
第 2 行 n 个正整数,表示元素 a[1] ~ a[n],每两个数之间用一个空格分隔。
第 3 行 1 个正整数 x,1≤x≤2000000。
输出
一行一个整数,表示这样的数对个数。
样例输入
95 12 7 10 9 1 2 3 1113
样例输出
3
本来想枚举de,但数据点太大,60分时间超限了。。。
还是得用二分,先快排,用函数也OK。
变量i循环,i=0--n-1,左指标=i+1,右指标=n-1,二分查找能与a[i]和为x的数,并将其附近符合的数也算入ans。
最后根据判断移动指标就行...
就这?
代码如下:
#include <bits/stdc++.h>using namespace std;int a[100001], n, x, ans;main(){freopen("sumx.in","r",stdin);freopen("sumx.out","w",stdout);scanf("%d", &n);for (int i = 0; i < n; i++){scanf("%d", &a[i]);}scanf("%d", &x);sort(a, a + n);for (int i = 0; i < n; i++){long mb = x - a[i];int l = i + 1, r = n - 1;while (l <= r){int mid = (l + r) / 2;if (a[mid] == mb){ans++;int ls = mid + 1;while (a[ls] == mb && ls < n){ls++;ans++;}ls = mid - 1;while (a[ls] == mb && ls >= 0){ls--;ans++;}break;}else if (a[mid] > mb){r = mid - 1;}else{l = mid + 1;}}}printf("%d", ans);}