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

题目

完善程序：

（郊游活动）有 $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;
}

②处应填（ ）

答案

M[i] < C[j]

题解

考点定位

本题（郊游租车第②空）考「容量比较」,对应大纲 4.3.1 二分+贪心（难度【4】）。

解题过程

②处贪心判定当前人能否上当前车：

``cpp if (M[i] < C[j]) ``

（严格小于——体重小于车容量限制。）答案：M[i] < C[j]。

易错提醒

① < 与 ≤ 的取舍来自题目「限乘」语义；② 不满足则换下一辆车（j++）。