问题 J: 2016J-完善2-二分-郊游活动
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:10
解决:5
题目描述
#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 名同学参加学校组织的郊游活动,已知学校给这 n 名同学的郊游总经费为 A 元,与此同时第 i 位同学自己携带了 M_i 元。为了方便郊游,活动地点提供 B(≥n) 辆自行车供人租用,租用第 j 辆自行车的价格为 Cj 元,每位同学可以使用自己携带的钱或者学校的郊游经费,为了方便账务管理,每位同学只能为自己租用自行车,且不会借钱给他人,他们想知道最多有多少位同学能够租用到自行车。
本题采用二分法。对于区间 [l, r] ,我们取中间点 mid 并判断租用到自行车的人数能否达到 mid。判断的过程是利用贪心算法实现的。
本题采用二分法。对于区间 [l, r] ,我们取中间点 mid 并判断租用到自行车的人数能否达到 mid。判断的过程是利用贪心算法实现的。