郊游活动）有 n 名同学参加学校组织的郊游活动，已知学校给这 n 名同学的郊游总经费为 A 元，与此同时第 i 位同学自己携带了 M_i元。为了方便郊游，活动地点提供 B(≥n) 辆自行车供人租用，租用第 j 辆自行车的价格为 C_j元，每位同学可以使用自己携带的钱或者学校的郊游经费，为了方便账务管理，每位同学只能为自己租用自行车，且不会借钱给他人，他们想知道最多有多少位同学能够租用到自行车。（第四、五空 2.52.5 分，其余 33 分）

本题采用二分法。对于区间 [l,r] ，我们取中间点 midmid 并判断租用到自行车的人数能否达到 mmid。判断的过程是利用贪心算法实现的。

原始数据：

序号	1	2	3	4	5	6	7	经费
同学携带的钱数	3	9	4	5	2	6		6
自行车租用价格	10	7	15	8	13	3	5

算法：
第1个逻辑步骤：对同学和车两个序列排序(快速排序)
第2个逻辑步骤：查找能满足同学(二分法)
第3个逻辑步骤：用钱多的同学去租最便宜的自行车，经费是否够用(贪心算法)

序号	1	2	3	4	5	6	7	经费
同学携带的钱数	2	3	4	5	6	9		6
自行车租用价格	3	5	7	8	10	13	15

#include <iostream>
using namespace std;
#define MAXN 1000000
//n是同学数，B是自行车数量，M[]是自己带的钱，C[]是车的钱
int n,B,A,M[MAXN],C[MAXN],l,r,ans,mid;
//从钱多的同学去租便宜的自行车
bool check(int nn){ //check判断nn是指同学可以有自行车
    int count=0,i,j;
    i=n-nn+1; //反着数，因为是从钱多的同学配自行车
    j=1;
    while(i<=n){   
        if(M[i]<C[j]) //如果学生的钱不够
        count+=C[j]-M[i]; //count是补了多少钱，累加
        i++;
        j++;
    }
     return  count<=A; //保证钱够
}
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(check(mid)){
            ans=mid;
            l=mid+1;
        }else
        r=mid-1;
    }
   
    
    cout<<ans<<endl;
    return 0;
}

Previous Topic

Back to Lesson

Next Quiz