问题 C: 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。判断的过程是利用贪心算法实现的。