太戈編程655題
題目描述：
有n輛車大甩賣，第i輛車售價a[i]元。有m個人帶著現(xiàn)金來申請購買，第i個到現(xiàn)場的人帶的現(xiàn)金為b[i]元，只能買價格不超過其現(xiàn)金額的車子。你是大賣場總經(jīng)理，希望將車和買家盡量多地進行一對一配對，請問最多賣出多少輛車？
貪心
貪心法模板：
比如說：每次挑最便宜的車賣給貧窮的人，……
相信大家第一個想到的思路就是二重for循環(huán)，第一層int i=1;i<=m;i++，第二層int j=1;j<=n;j++，時間復雜度O(n^2)。但是一看數(shù)據(jù)規(guī)模，n,m<=200000，也就是運行40000000000，四百億，幾乎不可能。這一下子，大家就想到了傳說中的“蠕動區(qū)間”。代碼來咯，
#include <bits/stdc++.h>
using namespace std;
const int N=200009;
int n,m,a[N],b[N];
int main(){
freopen("car2.in","r",stdin);
freopen("car2.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>b[i];
sort(a+1,a+1+n);
sort(b+1,b+1+m);
int cnt=0,i=1,j=1;
while(i<=n&&j<=m){
if(a[i]<=b[j]){
i++;
j++;
cnt++;
}else j++;
}
cout<<cnt<<endl;
return 0;
}太戈編程656題
題目描述：
有n輛車大甩賣，第i輛車售價a[i]元。有m個人帶著現(xiàn)金來申請購買，第i個到現(xiàn)場的人帶的現(xiàn)金為b[i]元。你是大賣場總經(jīng)理，可以將車和買家自由配對。如果買家的現(xiàn)金低于配對車的售價時，你有權力借錢給買家，但是總的借款額度不可以超過f。注意：買家之間不會互相借錢。請問通過你的配對和借款，剩下沒買到車的人最少有幾人？
二分+貪心
思路：要讓沒買到車的人最少，相當于要求買到車的人最多。二分枚舉答案x，OK函數(shù)判斷賣出x輛車是否可行（最優(yōu)化問題→可行性問題），而判斷的方法就要用到貪心
bool OK(int x){
int sum=0;
for(int i=0;i<=x;i++){
if(a[i]>b[m-x+i]) sum+=a[i]-b[m-x+i];
if(sum>f) return 0;
}
return 1;
}?
int main(){
freopen("car3.in","r",stdin);
freopen("car3.out","w",stdout);
cin>>n>>m>>f;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<m;i++) cin>>b[i];
sort(a,a+n);
sort(b,b+m);
int l=0,r=min(n,m),ans=0;
while(l<=r){
int mid=l+(r-l)/2;
if(OK(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
cout<<m-ans<<endl;
return 0;
}太戈編程1662題
自己獨立思考……文章來源：http://www.zghlxwxcb.cn/news/detail-784211.html
cin>>n>>d;
for(int i=1;i<=n;i++) cin>>x[i];
sort(x+1,x+n+1);
int cnt=0;
for(int i=1;j=2;i<=n-1;i++){
while(j<=n&&x[j]-x[i]<d) j++;
cnt+=j-i-1;
}
cout<<cnt<<endl;希望這些對大家有用，三連必回文章來源地址http://www.zghlxwxcb.cn/news/detail-784211.html
到了這里，關于Peter算法小課堂—貪心與二分的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
