icpc:problems:luogup1678
problems | |
---|---|
名称 | 烦恼的高考志愿 |
题目编号 | P1678 |
题目链接 | luogu.com.cn/… |
来源 | Luogu |
算法分类 | 二分, 二分_例题 |
难易程度 | 容易 |
烦恼的高考志愿
想法
二分查找第一个大于该数的数,特判 l==1
的情况。注意sum的类型为 long long int
。
代码实现
#include<cstdio> #include<algorithm> using namespace std; const int N = 100001; int line1[N], line2[N]; long long int sum; int main() { int n, m; scanf("%d %d", &n, &m); for(int i=1; i<=n; i++) scanf("%d", &line1[i]); for(int i=1; i<=m; i++) scanf("%d", &line2[i]); sort(line1+1, line1+1+n); for(int i=1; i<=m; i++) { int l = 1, r = n, mid, val = line2[i]; while(l < r) { mid = (l + r) / 2; if(line1[mid] < val) l = mid+1; else r = mid; } if(l == 1) { sum += abs(line1[l] - val); } else { sum += min(abs(line1[l]-val), abs(line1[l-1]-val)); } } printf("%lld", sum); return 0; }
/app/www/public/data/pages/icpc/problems/luogup1678.txt · 最后更改: 2024/01/25 11:31 由 温婕莺