P1678. 烦恼的高考志愿

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 176 阅读时长 ≈ 1 分钟

考点

  • 二分

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>

using namespace std;

const int LEN = 1e5 + 10;

typedef long long ll;

int arr[LEN];

int main()
{
    int m, n, in, idx;
    ll ans = 0;
    cin >> m >> n;
    for (int i = 0; i < m; ++i)
        cin >> arr[i];
    sort(arr, arr + m);
    while (n--)
    {
        cin >> in;
        int a = arr[idx = lower_bound(arr, arr + m, in) - arr];
        int b = arr[idx == 0 ? idx : idx - 1];
        ans += min(abs(in - a), abs(in - b));
    }
    cout << ans;
    return 0;
}

思路

题目实际上的含义，是每次输入一个数，要你找另外两个数：

  • 第一个大于等于它的数。lower_bound就可以做到
  • 小于它的数中最大（或者说仅次于它）的数。lower_bound结果的前一位就是

然后比较这两个数谁与输入的数差值最小即可