组合题5 个小题
已作答 0 / 5
完善程序:
(郊游活动)有 n 名同学参加学校组织的郊游活动,已知学校给这 n 名同学的郊游总经费为 A 元,与此同时第 i 位同学自己携带了 Mi 元。为了方便郊游,活动地点提供 B(≥n) 辆自行车供人租用,租用第 j 辆自行车的价格为 Cj 元,每位同学可以使用自己携带的钱或者学校的郊游经费,为了方便账务管理,每位同学只能为自己租用自行车,且不会借钱给他人,他们想知道最多有多少位同学能够租用到自行车。(第四、五空 2.5 分,其余 3 分)
本题采用二分法。对于区间 [l,r] ,我们取中间点 mid 并判断租用到自行车的人数能否达到 mid。判断的过程是利用贪心算法实现的。
1#include <iostream>2using namespace std;3#define MAXN 10000004 5int n, B, A, M[MAXN], C[MAXN], l, r, ans, mid;6 7bool check(int nn) {8 int count = 0, i, j;9 i = ①;10 j = 1;11 while (i <= n) {12 if(②)13 count += C[j] - M[i];14 i++;15 j++;16 }17 return ③;18}19 20void sort(int a[], int l, int r) {21 int i = l, j = r, x = a[(l + r) / 2], y;22 while (i <= j) {23 while (a[i] < x) i++;24 while (a[j] > x) j--;25 if (i <= j) {26 y = a[i]; a[i] = a[j]; a[j] = y;27 i++; j--;28 }29 }30if (i < r) sort(a, i, r);31if (l < j) sort(a, l, j);32}33 34int main() {35 int i;36 cin >> n >> B >> A;37 for (i = 1; i <= n; i++)38 cin >> M[i];39 for (i = 1; i <= B; i++)40 cin >> C[i];41 sort(M, 1, n);42 sort(C, 1, B);43 l = 0;44 r = n;45 while (l <= r) {46 mid = (l + r) / 2;47 if(④){48 ans = mid;49 l = mid + 1;50 }else51 r = ⑤;52 }53 cout << ans << endl;54 return 0;55}②处应填( )