題目鏈接：點擊查看

題目大意：給出n個人，每人有元錢，再給出m輛自行車，每輛車需要元錢才能騎，現在n個人有a元的共享資金，問最多可以騎多少量自行車，并且使每個人的花費總和最小(即盡可能多的使用共享資金)

題目分析：還是英語不好啊。。一開始以為題意是讓求最小騎多少量自行車和最多騎多少量自行車，然后想了半天也想不出來，去網上看了題解才發現題目問的是最多自行車和最小花費。。這樣就成了一個二分大水題了，先用貪心的思想將人的錢和自行車的錢升序排序，然后二分一下自行車的數量就行了，判斷條件就是讓前mid個自行車和后mid個人的錢一一比較，若自行車的錢比人的錢要多就記錄一下缺多少錢，最后和共享資金比較一下就行了

最后還要求一個最小花費，那么我們就將前mid個自行車的花銷累加一下，然后減去共享資金a元就是答案了，注意有個小細節，就是這個答案不能是負數，特判一下就行了

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int b[N],p[N];int main() { // freopen("input.txt","r",stdin);int n,m;LL a;scanf("%d%d%lld",&n,&m,&a);for(int i=1;i<=n;i++)scanf("%d",b+i);for(int i=1;i<=m;i++)scanf("%d",p+i);sort(b+1,b+1+n);sort(p+1,p+1+m);int l=0,r=min(n,m);int ans=0;while(l<=r){int mid=l+r>>1;LL sum=0;for(int i=0;i<mid;i++)if(p[mid-i]>b[n-i])sum+=p[mid-i]-b[n-i];if(sum<=a){ans=mid;l=mid+1;}elser=mid-1;}LL sum=0;for(int i=1;i<=ans;i++)sum+=p[i];sum=max(0LL,sum-a);printf("%d %lld\n",ans,sum);return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 363D Renting Bikes(二分+贪心)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。