NOIP 普及组初赛 · NOIP 2016 普及组初赛试题 第 28 题

完善程序：

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

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

二分答案：check(mid) 验证最有钱 mid 人配最便宜 mid 车，补贴≤A 则可行。

⚠️ 贪心起点：排序后最有钱的是 n−nn+1 到 n；补贴条件 M[i]<C[j]；二分不可行 r=mid−1。

考点：二分答案｜贪心策略

程序在做什么

二分最多能租到车的人数 mid。check(nn) 用贪心：最有钱的 nn 人配最便宜的 nn 辆车，不够的部分用学校经费补贴，总补贴≤A 则可行。