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

题目

完善程序：

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

①处应填（ ）

答案

n - nn + 1

题解

考点定位

本题（完善程序「郊游租车」第①空）考「二分下界调整」,对应大纲 4.3.1 二分（难度【4】）。

程序思路：二分「租最少车数 A」的答案；check(mid) 贪心验证 mid 辆车能否坐下所有人。

解题过程

①处贪心匹配中「上一辆车剩余空位延续」的计数：

``cpp count = n - nn + 1; // 口径依官方 ``

官方答案 n − nn + 1（新起点剩余可用座位的下标换算）。

易错提醒

① 二分答案 + 贪心 check 是标准组合：可行性有单调性（车越多越容易）；② 贪心匹配按「人数排序 + 车容量降序」逐个塞。