（郊游活动）有n名同学参加学校组织的郊游活动，已知学校给这 n名同学的郊游总经费为 A 元，与此 同时第 i 位同学自己携带了Mi元。为了方便郊游，活动地点提供 B(\ge n)B(≥n) 辆自行车供人租用，租用第j辆自行车的价格为 Cj元，每位同学可以使用自己携带的钱或者学校的郊游经费，为了方便账务管理，每位同学只能为自己租用自行车，且不会钱给他人，他们想知道最多有多少位同学能够租用到自行车。
本题采用二分法。对于区间 [l, r]， 我们取中间点 mid 并判断租用到自行车的人数能否达到 mid。判断的过程是利用贪心算法实现的。

include [HTML_REMOVED]

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;
}
本题主要考查分治算法和贪心算法。check函数使用贪心算法判断是否能够让 nn 个人租到自行车。贪心策略如下:让钱最多的 nn 个人租最便宜的 nn 辆车，其中，钱最少的租最便宜的车，钱第二少的租第二便宜的车，……钱最多的租最贵的车。

① n-nn+1 解释：这空比较难，题目里提示本题是贪心，让最有钱的同学去租最便宜车就可以减少学校A的消耗，j=1说明车是从便宜的开始，函数入口形式参数 nn 要让最有钱的 nn个同学去租。

② m[i]<c[j] 解释：此处下一行是统计钱不够的同学让学校出钱数量count，可以判断count是学校的支出；i说明当前 i 这位同学已经租下了第 j 辆车，即将尝试下一个同学，如果自己带的钱够租，那就不要让学校出钱，如果自己带的钱不够，那就让学校负担C[j]-M[j]的钱；j说明便宜的第 j辆车被租走了，即将尝试下一辆车。

③count<=A 解释：函数返回值是 bool，这里是关系运算，返回的应该是A够不够，④ 处成立的处理语句中mid+1说明 ④ 是成立的情况，所有count必须不大于A。

④ check(mid) 解释：l=mid+l说明租车的人还可以再多点，A还很充裕，钱够多。

⑤mid-1 解释：二分套路，租车的人太多，钱不够，要试试人更少的情况。