二分算法进阶

一、高考志愿

1、问题：现有 m 所学校，每所学校预计分数线是 a​。有 n 位学生，估分分别为 b。根据 n 位学生的估分情况，分别给每位学生推荐一所学校，要求学校的预计分数线和学生的估分相差最小（可高可低，毕竟是估分嘛），这个最小值为不满意度。求所有学生不满意度和的最小值。

2、输入格式：第一行读入两个整数 m, n。
第二行共有 m 个数，表示 m 个学校的预计录取分数。
第三行共有 n 个数，表示 n 个学生的估分成绩。

3、输出格式：输出一行，为最小的不满度之和。

4、解析思路：将分数线按升序排序，取中间值（中间的分数线）为临时的适合分数线，实际分数a若大于临时适合分数线，就看更高一点的学校的分数线，否则相反。若该学生的分数高于最高分数 线，则用分数减去分数线；若低于最低分数线，则用最低分数线减去分数；若处于中间某分数线附近，则根据绝对值最小的来取满意度

5、代码如下：

#include<bits/stdc++.h> using namespace std; int school[100001]; long long sum=0; int main() { int m,n; cin>>m>>n; for(int i=1;i<=m;i++) cin>>school[i]; sort(school+1,school+1+m); for(int i=0;i<n;i++) { int a,r=m,l=1,mid; cin >>a; while(l<r) { mid=(l+r)/2; if(a>=school[mid]) l=mid+1; else r=mid; } if(a<school[1]) { sum+=school[1]-a; } else if(l > m) { sum+=a - school[m]; } else { sum+=min(abs(school[l]-a),abs(school[l-1]-a)); } } printf("%lld",sum); return 0; }

二、木材加工

1、问题：木材厂有 n 根原木，现在想把这些木头切割成 k 段长度均为 l 的小段木头（木头有可能有剩余）。
当然，我们希望得到的小段木头越长越好，请求出 l 的最大值。
木头长度的单位是 cm，原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。
例如有两根原木长度分别为 11 和 21，要求切割成等长的 6 段，很明显能切割出来的小段木头长度最长为 5。

2、输入格式：第一行是两个正整数n和k ，分别表示原木的数量，需要得到的小段的数量。
接下来 n 行，每行一个正整数 L，表示一根原木的长度。

3、输出格式：仅一行，即 l 的最大值。
如果连 1cm 长的小段都切不出来，输出 0

4、解析思路：将长度按降序排序，长度不够1cm直接输出0。从中间长度开始锯木头，用count计数，看锯出来的木头数量是否达标，达标则增加锯的长度，没达标就按上一长度（当前的r）来算。

5、代码如下：

#include<bits/stdc++.h> using namespace std; long long n,k,L[100006],sum,count_; bool cmp(int a,int b) { return a>b; } int main() { scanf("%lld%lld",&n,&k); for(int i=1;i<=n;i++) { cin>>L[i]; sum+=L[i]; } sort(L+1,L+1+n,cmp); if(sum<k) printf("0"); else { int l=1,r=L[1]; while(l<=r) { int mid=(l+r)/2; count_=0; for (int i=1;i<=n;i++) { count_+=L[i]/mid; if(count_>k||count_<=k&&L[i]<mid) break; } if(count_>=k) l=mid+1; else r=mid-1; } cout<<r; } return 0; }