建站公司前途,p2p网站建设报价,百度做销售网站多少钱,衡阳seo优化公司烦恼的高考志愿
题目背景
计算机竞赛小组的神牛 V 神终于结束了高考#xff0c;然而作为班长的他还不能闲下来#xff0c;班主任老 t 给了他一个艰巨的任务#xff1a;帮同学找出最合理的大学填报方案。可是 v 神太忙了#xff0c;身后还有一群小姑娘等着和他约会#x…烦恼的高考志愿
题目背景
计算机竞赛小组的神牛 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
对于 100 % 100\% 100% 的数据 1 ≤ n , m ≤ 100000 1\leq n,m\leq100000 1≤n,m≤100000估分和录取线 ≤ 1000000 \leq 1000000 ≤1000000 且均为正整数。
lower_bound函数
#includeiostream
#includealgorithmusing namespace std;
int m,n;
const int MAXN1e55;
int a[MAXN];
int main()
{cinmn;for(int i1;im;i)cina[i];sort(a1,am1);long long sum0;for(int i1;in;i){int score;cinscore;//lower_bound函数返回的是一个指针而数组名a也是一个指针所以相减能得到两指针之间的距离也就是score应该插入的位置从小到大顺序int tlower_bound(a1,am1,score)-a;if(tm1)//等于m1说明比数组a中所有的数都要大sumscore-a[m];else if(t1)//等于1说明比数组a中所有的数都要小suma[1]-score;else//否则返回的t就是他应该插入的下标当前数组的t位置也是第一个大于等于他的数summin(score-a[t-1],a[t]-score);} coutsumendl;return 0;
}二分
#includeiostream
#includealgorithm
using namespace std;
int m,n;
const int MAXN1e55;
int a[MAXN];
int main()
{cinmn;for(int i1;im;i)cina[i];sort(a1,am1);long long sum0;for(int i1;in;i){int score;cinscore;int l1;int rm;int mid;int ans;while(lr-1)//二分出两个值{mid(lr)/2;if(scorea[mid])lmid;elsermid;}if(abs(score-a[l])abs(a[r]-score))//判断这两个哪个离score近ansabs(score-a[l]);elseansabs(a[r]-score);sumans;} coutsumendl;return 0;
}
