P1678 烦恼的高考志愿-二分
P1678 烦恼的高考志愿-二分
https://www.luogu.com.cn/problem/P1678
题意
-
m个学校,n个学生。 每个学生都有成绩,每个学校都有分数线 给每个学生匹配上一个学校,使得分数线和学生成绩的绝对值最小。输出差值之和。
想法
-
二分+排序 先将分数线数组排序用于二分 找到最后一个<= p[i]的序号的学校,分别比较 l序号和l+1的序号学校的分数线。绝对值之差小的,便是答案。
// // Created by majoe on 2020/5/27. // https://www.luogu.com.cn/problem/P1678 #include <bits/stdc++.h> using namespace std; const int maxn = 100010; long long m , n ,ans; long long s[maxn],p[maxn]; int main(){ cin >> m >> n; for (int i = 0; i < m; ++i) { cin >> s[i]; } for (int i = 0; i < n; ++i) { cin >> p[i]; } sort(s,s+m); //找到最后一个<= p[i]的序号,分别比较 l序号和l+1的序号 for (int i = 0; i < n; ++i) { int l = 0 , r= m-1; while(l < r){ int mid = l + r + 1 >>1; if(s[mid]<= p[i]) l = mid; else r = mid -1 ; } ans += min(abs(p[i] - s[l]),abs(p[i]- s[l+1])); } cout << ans; return 0; }