ACM寒假第二讲

一、二分查找

设计思路

题目要求输入一个数字整数q代表q次查询，查询是否在之前的n个整数中出现过，若出现则输出“Yes”，否则输出“No”。典型的二分查找思路，对照资料即可得出代码。

设计代码

#include <iostream>
#include <vector>
using namespace std;

int Tsearch(const vector<int> &a, int l, int r, int x) {
	while (l < r) {
		int mid = (l + r) / 2;
		if (a[mid] >= x)
			r = mid;
		else
			l = mid + 1;
	}
	return l;
}

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int q;
	cin >> q;
	int x;
	for (int i = 0; i < q; i++) {
		cin >> x;
		int result = Tsearch(a, 0, n, x);
		if (a[result] == x) {
			cout << "Yes" << endl;
		} else {
			cout << "No" << endl;
		}
	}
	return 0;
}

二、A-B数对

设计思路

题目要求在一串整数中求满足A-B=C的数对（A，B），这边利用STL的二分查找函数upper_bound和lower_bound。并且进行思路转换，寻找满足B+C=A中A的个数，就是我们要求的数对个数。

设计代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int n, c;
	cin >> n >> c;
	vector<int>a(n);
	long long s = 0;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	sort(a.begin(), a.end());
	for (int i = 0; i < n; i++)
		s += upper_bound(a.begin(), a.end(), a[i] + c) - lower_bound(a.begin(), a.end(), a[i] + c);//关键，利用两个二分查找锁定目标A（即满足B+C的数字A）
	cout << s << endl;
	return 0;
}

三、分巧克力

设计思路

题目简单来说，就是给定N块巧克力，并给定它们的宽高，求出能够给K个小朋友的最大边长的巧克力。

容易想到，一块大块的巧克力可以切的块数为（宽/r）*（高/r），只需要用二分查找进行逼近，求出对应的r即可

设计代码

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, k, mid;
	cin >> n >> k;
	vector<int>h(n);
	vector<int>w(n);
	int ans = 0;
	for (int i = 0; i < n; i++) {
		cin >> h[i] >> w[i];
		ans = max(h[i], max(ans, w[i]));
	}
	int l = 0, r = 2 * ans;//原本从很大范围进行查找，因为这边已知边长，因此可以缩小范围
	while (l < r) {//l<r的模型
		ans = 0;
		mid = (l + r + 1) / 2;
		for (int i = 0; i < n; i++)
			ans += (h[i] / mid) * (w[i] / mid);
		if (ans >= k)//若所求块数大于小朋友人数，进行逼近
			l = mid;
		else//小于所求人数，右边减少一位进行缩小
			r = mid - 1;
	}
	cout << l;
	return 0;
}

四、卡牌

设计思路

这个题目主要要考虑可以手写的手牌数以及原本有的手牌数，以此来进一步确认我们所需要的二分查找的l与r，才能进一步利用l和r来逼近所求的套牌数，要注意本题需要开long long否则测试样例会超时。

设计代码

#include <bits/stdc++.h>
using namespace std;

int main() {
	long long n, k, l, r, ans;
	cin >> n >> k;
	long long need = 0;
	vector<long long>p(n), m(n);
	for (long long i = 0; i < n; i++) {
		cin >> p[i];
	}
	for (long long i = 0; i < n; i++) {
		cin >> m[i];
	}
	l = 1;
	r = 200000000;//先开很大的区间来确保全概况
	while (l <= r) {
		long long mid = (l + r) / 2;
		need = 0;//所求套牌数
		int flag = 0;//标记，为了应对特殊情况
		for (long long i = 0; i < n; i++) {
			if (mid - p[i] > m[i]) {//如果所需空白牌大于可以绘制的次数
				r = mid - 1;//缩小区间
				flag = 1;//标记
				break;
			}
			need += max(mid - p[i], 0ll);//累加空白牌的数目
		}
		if (flag)
			continue;//应对特殊情况，缩小后无需判断，故continue进行跳过
		if (need <= k) {
			ans = mid;
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	cout << ans;
	return 0;
}

五、学习总结

在这次C++代码中，系统性学习了二分查找的相关知识点和代码，也理解了之前不理解的一些小细节，并且认识到二分查找使用的范围其实还是很广泛的，尤其是对所求目标进行“逼近”的思想，很值得进一步深入思考。