0 of 1 Questions completed
Questions:
You have already completed the quiz before. Hence you can not start it again.
Quiz is loading…
You must sign in or sign up to start the quiz.
You must first complete the following:
0 of 1 Questions answered correctly
Your time:
Time has elapsed
You have reached 0 of 0 point(s), (0)
Earned Point(s): 0 of 0, (0)
0 Essay(s) Pending (Possible Point(s): 0)
28. (郊游活动)有 n名同学参加学校组织的郊游活动,已知学校给这 n 名同学的郊游总经费为 A 元,与此 同时第 i 位同学自己携带了 M[i] 元。为了方便郊游,活动地点提供 B(≥n) 辆自行车供人租用,租用第 j 辆自行车的价格为 C[j] 元,每位同学可以使用自己携带的钱或者学校的郊游经费,为了方便账务管理,每位同学只能为自己租用自行车,且不会借钱给他人,他们想知道最多有多少位同学能够租用到自行车。
本题采用二分法。对于区间 [l, r]
, 我们取中间点 mid
并判断租用到自行车的人数能否达到 mid
。判断的过程是利用贪心算法实现的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#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; } |
填空位置 ①
填空位置 ②:
填空位置 ③:
填空位置 ④:
填空位置 ⑤: