题库 模拟押题卷 题目列表 完善程序:(郊游活动)有 n 名同学参加学校组织的郊...
组合题

完善程序:

(郊游活动)有 n 名同学参加学校组织的郊游活动,已知学校给这 n 名同学 的郊游总经费

为 A 元,与此同时第 i 位同学自己携带了 M_i元。为了方便郊 游,活动地点提供 B(≥n)辆

自行车供人租用,租用第 j辆自行车的价格为 C_j元,每位同学可以使用自己携带的钱或者学

校的郊游经费,为了方便账务管 理,每位同学只能为自己租用自行车,且不会借钱给他人,

他们想知道最多有多少位同学能够租用到自行车。

本题采用二分法。对于区间 [l, r] ,我们取中间点 mid 并判断租用到自行车的人数能否达到

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 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;
}

第一空(3分):_______________________

第二空(3分):_______________________

第三空(3分):_______________________

第四空(2.5分):_______________________

第五空(2.5分):_______________________

第 1 题 填空
第 2 题 填空
第 3 题 填空
第 4 题 填空
第 5 题 填空
题目信息
完善程序
-
正确率
0
评论
34
点击
QQ
微信