烦恼的高考志愿
题目背景
计算机竞赛小组的神牛 V 神终于结束了高考,然而作为班长的他还不能闲下来,班主任老 t 给了他一个艰巨的任务:帮同学找出最合理的大学填报方案。可是 v 神太忙了,身后还有一群小姑娘等着和他约会,于是他想到了同为计算机竞赛小组的你,请你帮他完成这个艰巨的任务。
题目描述
现有 m m m 所学校,每所学校预计分数线是 a i a_i ai。有 n n n 位学生,估分分别为 b i b_i bi。
根据 n n n 位学生的估分情况,分别给每位学生推荐一所学校,要求学校的预计分数线和学生的估分相差最小(可高可低,毕竟是估分嘛),这个最小值为不满意度。求所有学生不满意度和的最小值。
输入格式
第一行读入两个整数 m , n m,n m,n。 m m m 表示学校数, n n n 表示学生数。
第二行共有 m m m 个数,表示 m m m 个学校的预计录取分数。第三行有 n n n 个数,表示 n n n 个学生的估分成绩。
输出格式
输出一行,为最小的不满度之和。
样例 #1
样例输入 #1
4 3
513 598 567 689
500 600 550
样例输出 #1
32
提示
数据范围:
对于 30 % 30\% 30% 的数据, 1 ≤ n , m ≤ 1000 1\leq n,m\leq1000 1≤n,m≤1000,估分和录取线 ≤ 10000 \leq10000 ≤10000;文章来源:https://www.toymoban.com/news/detail-432925.html
对于 100 % 100\% 100% 的数据, 1 ≤ n , m ≤ 100000 1\leq n,m\leq100000 1≤n,m≤100000,估分和录取线 ≤ 1000000 \leq 1000000 ≤1000000 且均为正整数。文章来源地址https://www.toymoban.com/news/detail-432925.html
lower_bound函数
#include<iostream>
#include<algorithm>
using namespace std;
int m,n;
const int MAXN=1e5+5;
int a[MAXN];
int main()
{
cin>>m>>n;
for(int i=1;i<=m;i++)
cin>>a[i];
sort(a+1,a+m+1);
long long sum=0;
for(int i=1;i<=n;i++)
{
int score;
cin>>score;
//lower_bound函数返回的是一个指针,而数组名a也是一个指针,所以相减能得到两指针之间的距离也就是score应该插入的位置(从小到大顺序)
int t=lower_bound(a+1,a+m+1,score)-a;
if(t==m+1)//等于m+1说明比数组a中所有的数都要大
sum+=score-a[m];
else if(t==1)//等于1说明比数组a中所有的数都要小
sum+=a[1]-score;
else//否则返回的t就是他应该插入的下标,当前数组的t位置也是第一个大于等于他的数
sum+=min(score-a[t-1],a[t]-score);
}
cout<<sum<<endl;
return 0;
}
二分
#include<iostream>
#include<algorithm>
using namespace std;
int m,n;
const int MAXN=1e5+5;
int a[MAXN];
int main()
{
cin>>m>>n;
for(int i=1;i<=m;i++)
cin>>a[i];
sort(a+1,a+m+1);
long long sum=0;
for(int i=1;i<=n;i++)
{
int score;
cin>>score;
int l=1;
int r=m;
int mid;
int ans;
while(l<r-1)//二分出两个值
{
mid=(l+r)/2;
if(score>=a[mid])
l=mid;
else
r=mid;
}
if(abs(score-a[l])<abs(a[r]-score))//判断这两个哪个离score近
ans=abs(score-a[l]);
else
ans=abs(a[r]-score);
sum+=ans;
}
cout<<sum<<endl;
return 0;
}
到了这里,关于烦恼的高考志愿的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!