标签：ch space T7 ll bound le 90 include Typical

ATCoder Typical 90 T7 CP Classes

这道题没有英文版

题意

\(ABC\)竞技编程补习班中有 \(N\) 个班级。第 \(i \space \space(1 \le i \le N)\) 个班级想要招收对象排名为 \(A_i\) 的学生。

现在有 \(Q\) 个学生参加补习班。第 \(j \space \space(1 \le j \le Q)\) 个学生的排名为 \(B_j\) 。每个学生对进入与自己不匹配的等级的班级感到不满。关于每个学生，对不满度的定义如下：

对象排名 \(a\) 和自己的排名 \(b\) 的差的绝对值，即 \(|a - b|\)。

请输出每个学生的不满度的最小值。

\[\begin{aligned} 1 \le N \le 300000\\ 1 \le Q \le 300000\\ 0 \le A_i \le 10^9\\ 0 \le B_i \le 10^9\\ 输入均为整数 \end{aligned} \]

大致思路

很明显，要排序后二分查找出最接近的那个。

用algorithm头文件中的lower_bound()或upper_bound函数即可：

我们根据题意选用lower_bound

for (int i = 1; i <= Q; ++i) {
        int idx = lower_bound(a + 1, a + n + 1, b[i]) - a;
        cout << min(abs(b[i] - a[idx]),
                    abs(b[i] - a[idx - 1]))
                  << '\n';
}

但是lower_bound^[1]在找不到是会返回尾指针，所以我们需要判断一下是否合法即可。

AC Code

// G.cpp 3s 1G
// 007 - CP Classes
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iostream>

using namespace std;
using ll = long long;
const int N = 3e6 + 5;
const int INF = 0x7fffffff;

ll n, Q;
ll a[N], b[N];

inline ll read() {
    ll x = 0;
    int f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

signed main() {
    // #1 : Input

    n = read();
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
    }
    Q = read();
    for (int i = 1; i <= Q; ++i) {
        b[i] = read();
    }

    // #2 : Sort
    sort(a + 1, a + n + 1);

    // #3 : Binary Search
    for (int i = 1; i <= Q; ++i) {
        int idx = lower_bound(a + 1, a + n + 1, b[i]) - a;
        cout << min(idx <= n ? abs(b[i] - a[idx]) : INF,
                    idx >= 2 ? abs(b[i] - a[idx - 1]) : INF)
             << '\n';
    }
    return 0;
}

---

1. 关于lower_bound的用法，参见用法 ↩︎

标签：ch,space,T7,ll,bound,le,90,include,Typical
From： https://www.cnblogs.com/lstylus/p/18104614