1.2016年NOIP普及组初赛最后一题郊游活动题解

2016年NOIP普及组初赛最后一题郊游活动题解

       本题首先要读透题目，源码题意最后是源码交叉指标源码要求得最多有多少位同学能够租到自行车，则所有钱都用来在租车上了。源码条漫源码钱的源码好多粉源码来源有两方面

        总钱数=Mi+A

       租车的人在自己钱不够用的情况下，可以动用公共基金A,源码rn商城源码只要公用基金够用，就能租到车。源码双人台球源码编程者利用贪心算法计算在租车过程中把欠款都累加在count中，源码只要count<=A,源码就能继续租车。

       源代码如下：#include<iostream>

       using namespace std;

       #define MAXN

       int n,源码B,A,M[MAXN],C[MAXN],l,r,ans,mid;

       bool check(int nn)

       { int count=0,i,j;

        i=n-nn+1;

        j=1;

        while(i<=n)

       { if(C[j]>M[i])count+=C[j]-M[i];

        i++; j++;

        }

        return A>=count;

       }

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