POJ 07:和为给定数（二分枚举）

POJ 07:和为给定数（二分枚举）

“ Ctrl AC！一起 AC！”

题目：忘题戳这

分析：这是一道典型的二分查找题。我们先对数组排序，再遍历数组。我们要求的和为m，当前遍历到的数为num[i]，我们用一个变量保存两者之差 即：delt=m-num[i]，我们只需要在这个数组里面找有没有delt就行。因为我们的数组已经从小到大排好序了，所以第一个找到的就是答案。

AC代码：

#include
#include
using namespace std;
int num[100005];
int delt;//二分查找的数
int doublecut(int left, int right) {//二分函数
	while (left < right) {
		int mid = (left + right) / 2;
		if (delt > num[mid]) left = mid + 1;
		else right = mid;
	}
	return right;
}
int main() {
	int n, m; cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> num[i];
	}
	sort(num, num + n);
	cin >> m;
	int flag = 0;
	int i, last;
	for (i = 0; i < n; i++) {
		delt = m - num[i];//生成要查找的数
		int left = 0, right = n-1, mid;
		last = doublecut(left, right);
		if (delt == num[last] && last != i) {//满足条件，last！=i！！！
			flag = 1;
			break;
		}
	}
	if (flag) {
		cout << num[i] << " " << num[last] << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}

感谢阅读！！！

“ Ctrl AC！一起 AC！”