![](https://iknow-base.cdn.bcebos.com/lxb/notice.png)
求NOIP2016年普及组初赛最后一题的详细算法 20
求以下代码的详细算法(郊游活动)有n名同学参加学校组织的郊游活动,已知学校给这n名同学的郊游总经费为A元,与此同时第i位同学自己携带了Mi元。为了方便郊游,活动地点提供B...
求以下代码的详细算法(郊游活动)有 n 名同学参加学校组织的郊游活动,已知学校给这 n 名同学 的郊游总经费为 A 元,与此同时第 i 位同学自己携带了 Mi 元。为了方便郊 游,活动地点提供 B(≥n)辆自行车供人租用,租用第 j 辆自行车的价格为 Cj 元,每位同学可以使用自己携带的钱或者学校的郊游经费,为了方便账务管 理,每位同学只能为自己租用自行车,且不会借钱给他人,他们想知道最多 有多少位同学能够租用到自行车。(第四、五空 2.5 分,其余 3 分) 本题采用二分法。对于区间[l, r],我们取中间点 mid 并判断租用到自行 车的人数能否达到 mid。判断的过程是利用贪心算法实现的。#include <iostream>using namespace std;#define MAXN 1000000int n, B, A, M[MAXN], C[MAXN], l, r, ans, mid;bool check(int nn) {int count = 0, i, j;i = (1) ;j = 1;while (i <= n) {if ( (2) )count += C[j] - M[i];i++;j++;}return (3) ;}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 ( (4) ) {ans = mid;l = mid + 1;} elser = (5) ;}cout << ans << endl;return 0;}
展开
1个回答
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询