广告制作公司开票范围,搜索引擎优化行业,wordpress 百度软件,技术先进的网站建设太戈编程655题
题目描述#xff1a; 有n辆车大甩卖#xff0c;第i辆车售价a[i]元。有m个人带着现金来申请购买#xff0c;第i个到现场的人带的现金为b[i]元#xff0c;只能买价格不超过其现金额的车子。你是大卖场总经理#xff0c;希望将车和买家尽量多地进行一对一配对…太戈编程655题
题目描述 有n辆车大甩卖第i辆车售价a[i]元。有m个人带着现金来申请购买第i个到现场的人带的现金为b[i]元只能买价格不超过其现金额的车子。你是大卖场总经理希望将车和买家尽量多地进行一对一配对请问最多卖出多少辆车
贪心
贪心法模板
比如说每次挑最便宜的车卖给贫穷的人……
相信大家第一个想到的思路就是二重for循环第一层int i1;im;i第二层int j1;jn;j时间复杂度O(n^2)。但是一看数据规模n,m200000也就是运行40000000000四百亿几乎不可能。这一下子大家就想到了传说中的“蠕动区间”。代码来咯
#include bits/stdc.h
using namespace std;
const int N200009;
int n,m,a[N],b[N];
int main(){freopen(car2.in,r,stdin);freopen(car2.out,w,stdout);cinnm;for(int i1;in;i) cina[i];for(int i1;im;i) cinb[i];sort(a1,a1n);sort(b1,b1m);int cnt0,i1,j1;while(injm){if(a[i]b[j]){i;j;cnt;}else j;}coutcntendl;return 0;
}
太戈编程656题
题目描述 有n辆车大甩卖第i辆车售价a[i]元。有m个人带着现金来申请购买第i个到现场的人带的现金为b[i]元。你是大卖场总经理可以将车和买家自由配对。如果买家的现金低于配对车的售价时你有权力借钱给买家但是总的借款额度不可以超过f。注意买家之间不会互相借钱。请问通过你的配对和借款剩下没买到车的人最少有几人
二分贪心
思路要让没买到车的人最少相当于要求买到车的人最多。二分枚举答案xOK函数判断卖出x辆车是否可行最优化问题→可行性问题而判断的方法就要用到贪心 bool OK(int x){int sum0;for(int i0;ix;i){if(a[i]b[m-xi]) suma[i]-b[m-xi];if(sumf) return 0; }return 1;
} int main(){freopen(car3.in,r,stdin);freopen(car3.out,w,stdout);cinnmf;for(int i0;in;i) cina[i];for(int i0;im;i) cinb[i];sort(a,an);sort(b,bm);int l0,rmin(n,m),ans0;while(lr){int midl(r-l)/2;if(OK(mid)) ansmid,lmid1;else rmid-1;}coutm-ansendl;return 0;
}
太戈编程1662题
自己独立思考……
cinnd;
for(int i1;in;i) cinx[i];
sort(x1,xn1);
int cnt0;
for(int i1;j2;in-1;i){while(jnx[j]-x[i]d) j;cntj-i-1;
}
coutcntendl;
希望这些对大家有用三连必回
