Zenn
💪

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

2022/01/09に公開
競技プログラミング
AtCoder
典型90問
チャレンジ
tech

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();

解答

#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;
}

Discussion