CodeForces 363D 【二分+贪心】

思路：

一开始是没有办法贪心的，但是答案是可以二分的，因为窝能买k辆车的话，窝就一定能买k-1辆车；而且我最好就是拿手上钱较多的那些人去买价格便宜的车，这样肯定是能买到最多的车，而且花的少，因为对于要买的车公共钱的话够得话，那就直接公共钱付了就行，而要付出的钱是一定要付的。

所以直接二分答案。

然后人的总花费=最有钱的那些人去买最便宜的那些车的情况；

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int,int>PII;

const double eps=1e-5;

const double pi=acos(-1.0);

const int INF=0x3f3f3f3f;

const int N=1e5+10;

LL b[N],p[N],a;

int main()

{

    int n,m;

    scanf("%d%d%lld",&n,&m,&a);

    for(int i=1;i<=n;i++)

        scanf("%lld",&b[i]);

    for(int i=1;i<=m;i++)

        scanf("%lld",&p[i]);

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

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

    int ans=0,cas=100;

    int left=0,right=min(n+1,m+1);

    while(left<right&&cas--)

    {

        int mid=(left+right)/2;

        LL res=0;

        for(int i=1;i<=mid;i++)

        {

            if(b[n+1-i]<p[mid+1-i])   //最有钱的几个人去买最便宜的车以至于能买到最多数量的车；

                res+=(p[mid+1-i]-b[n+1-i]);

        }

        if(res<=a)

        {

            left=mid;

            ans=mid;

        }

        else

            right=mid;

    }

    printf("%d",ans);

    LL pay_out=0;

    for(int i=1;i<=ans;i++)

    {

        if(b[n+1-i]<=p[ans+1-i])

        {

            pay_out+=b[n+1-i];

            a-=(p[ans+1-i]-b[n+1-i]);

        }

        else

            pay_out+=p[ans+1-i];

    }

    printf(" %lld",max(0LL,pay_out-a));

    return 0;

}

巴特西

CodeForces 363D 【二分+贪心】

最新文章

热门文章