【チャレンジ記録】競プロ典型 90 問_7問目

Atcoderの典型90問のチャレンジ記録です。

問題　007 - CP Classes（★3）

https://atcoder.jp/contests/typical90/tasks/typical90_g

考えたこと

• 順番は関係ないので、ソートして一番近い値を探すことにした。
• 探す値以上のクラスiと、それより一つ小さいレートのクラスi-1を最後に比較した。
• -inf,infのクラスを用意して両端のクラスが選択された時も対応できるようにした。
• lower_boundは調べる値以上、upper_boundは調べる値より大きな値のポインタを返す。
• lower_boundはイテレータを返すので、返ってくるのは番地。インデックスを取得したい場合は、vectorの先頭の配列を引いてあげる必要がある。

auto y = lower_bound(a.begin(),a.end(),x) - a.begin();

• autoとしているが、intでも通った。
• lower_bound, upper_boundは下記リンク先が参考になった
  https://qiita.com/kontotto/items/c718ec114b1532a2d159

解答

#include <bits/stdc++.h>
#include <atcoder/all>
#include <vector>
#include <cstdint>
#define FOR(i,l,r) for(int i=(l);i<(r);++i)
#define RFOR(i,l,r) for(int i=(l);i>=(int)(r);i--)
#define rep(i,n)  FOR(i,0,n)
#define rrep(i,n)  RFOR(i,n-1,0)

#define int long long
#define ll long long
using namespace std;
using namespace atcoder;
const ll MX = 1e6;
const ll inf = 1e13;
const int mod = 1000000007;
signed main(){
    int n;
    cin>>n;
    vector<int> a(n+2);
    a[0]=-inf;
    rep(i,n) cin>>a[i+1];
    a[n+1]=inf;
    sort(a.begin(),a.end());
    int m;
    cin>>m;
    rep(i,m) {
        int x;
        cin>>x;
        auto y = lower_bound(a.begin(),a.end(),x) - a.begin();
        cout << min(abs(a[y]-x),abs(a[y-1]-x)) << endl;
    }    
    return 0;
}