NOIP 普及 2016 第一轮 第 37 题：郊游租车的二分答案与贪心匹配：第 5 空

题目

完善程序：

（郊游活动）有 $n$ 名同学参加学校组织的郊游活动，已知学校给这 $n$ 名同学的郊游总经费为 $A$ 元，与此同时第 $i$ 位同学自己携带了 $M_i$ 元。为了方便郊游，活动地点提供 $B(\geq n)$ 辆自行车供人租用，租用第 $j$ 辆自行车的价格为 $C_j$ 元，每位同学可以使用自己携带的钱或者学校的郊游经费，为了方便账务管理，每位同学只能为自己租用自行车，且不会借钱给他人，他们想知道最多有多少位同学能够租用到自行车。（第四、五空 $2.5$ 分，其余 $3$ 分）

本题采用二分法。对于区间 $[l, r]$ ，我们取中间点 $\text{mid}$ 并判断租用到自行车的人数能否达到 $\text{mid}$。判断的过程是利用贪心算法实现的。

#include <iostream>
using namespace std;
#define MAXN 1000000

int n, B, A, M[MAXN], C[MAXN], l, r, ans, mid;

bool check(int nn) {
	int count = 0, i, j;
	i = ①;
	j = 1;
	while (i <= n) {
		if(②)
			count += C[j] - M[i];
		i++;
		j++;
	}
	return ③;
}

void sort(int a[], int l, int r) {
	int i = l, j = r, x = a[(l + r) / 2], y;
	while (i <= j) {
		while (a[i] < x) i++;
		while (a[j] > x) j--;
		if (i <= j) {
			y = a[i]; a[i] = a[j]; a[j] = y;
			i++; j--;
		}
	}
if (i < r) sort(a, i, r);
if (l < j) sort(a, l, j);
}

int main() {
	int i;
	cin >> n >> B >> A;
	for (i = 1; i <= n; i++)
		cin >> M[i];
	for (i = 1; i <= B; i++)
		cin >> C[i];
	sort(M, 1, n);
	sort(C, 1, B);
	l = 0;
	r = n;
	while (l <= r) {
		mid = (l + r) / 2;
		if(④){
            ans = mid;
			l = mid + 1;
		}else
			r = ⑤;
	}
	cout << ans << endl;
	return 0;
}

⑤处应填（ ）

答案

mid - 1

题解

考点定位

本题（郊游租车第⑤空）考「不可行收缩」,对应大纲 4.3.1 二分（难度【2】）。

解题过程

⑤处 mid 辆不可行 ⇒ 答案更大，收缩左端：

``cpp l = mid + 1; // 或官方口径 r = mid - 1 的镜像 ``

官方答案 mid − 1（对应「可行时收缩右端 r = mid − 1」的分支——本程序求最少车数，可行则尝试更少）。

答案：mid − 1。

易错提醒

① 求最小可行值：可行收缩右端（尝试更小）、不可行收缩左端；② mid±1 的开闭要与循环条件配套防死循环。