D. Renting
Bikes

读懂题后一开始和队友都以为是贪心。可是贪心又怎么贪呢。。我们无法确定到底能买多少车但肯定是最便宜的前x辆。除了公共预算每个人的钱只能自己用，也无法确定每个人买哪一辆车。。比赛快结束时我去看最后一题，队友还在 想，突然他想到了用二分的思路，然后验证了一下是正确的，但时间不够了。今天回来就这道题都快写了两小时了。

题意：n个人，每个人自己有一定的钱，还有公共的预算。m辆自行车，每辆车有一定的价格。求最多能租几辆车并且用的私房钱的总数最少。

思路：结束后百度了一下果然是二分。二分能买多少辆车，然后看看是否符合条件，然后再取总私房钱花的最少的。

但这种二分题真的写起来很痛苦了，明明思路很清晰，就是边界问题或者各种细节问题处理起来相当费时间。

const int N=2e5+7;

int n,m;

ll ans,k,a[N],b[N];

ll fun(int x)

{

    if(m<x) return 0;

    ll sum=0,kk=k;//sum表示用的私房钱总数，kk表示剩余的预算；

    for(int i=n; i>=1&&x>=1; i--,x--)

    {

        if(a[i]>=b[x]) sum+=b[x];//先用自己的钱垫，最后剩余的预算再补回来；

        else

        {

            if(kk>0&&a[i]+kk>=b[x])

            {

                sum+=a[i];

                kk-=b[x]-a[i];//用预算补；

            }

            else return 0;

        }

    }

    if(kk<0||x>=1) return 0;

//    printf("%I64d %I64d\n",sum,kk);

    ans=sum-kk<=0?0:min(ans,sum-kk);

    return 1;

}

int main()

{

    while(~scanf("%d%d%I64d",&n,&m,&k))

    {

        for(int i=1; i<=n; i++) scanf("%I64d",&a[i]);

        for(int i=1; i<=m; i++) scanf("%I64d",&b[i]);

        sort(a+1,a+n+1);

        sort(b+1,b+m+1);

        if(a[n]+k<b[1])

        {

            printf("0 0\n");

            continue;

        }

        ans=INF;

        int l=1,r=n;

        while(l<=r)

        {

            int mid=(l+r)/2;

//            printf("%d\n",mid);

            if(fun(mid)) l=mid+1;

            else r=mid-1;

        }

        ans=INF;

        ll t1=fun(l),t2=fun(r);

        if(t1&&!t2) printf("%d %I64d\n",l,ans);

        else printf("%d %I64d\n",r,ans);

    }

    return 0;

}

//1 1 2

//1

//2

//******************************************

//*****************   LYQ    ***************

//*****************   YES    ***************

//*UserID: secrecy                         *

//*RunOJ:                                  *

//*RunID:                                  *

//*Submit time:                            *

//*Language: G++                           *

//*Result: Accepted                        *

//*time:                                   *

//*Memory:                                 *

//*Length:                                 *

//*School: NYIST                           *

//*Blog: http://blog.csdn.net/nyist_tc_lyq *

//*QQ: 1759421378                          *

//*Tel: 13037635630                        *

//*****************************************/

思路真的很清晰，可能是代码能力还是比较低，一上午就做了这一个题。。