앳코더90 - 007 - CP Classes（★3）

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

007 - CP Classes（★3）

 

N개의 A값을 가진 class가 나온다.

B점수가 class를 들어갈때 오차가 최소가 되게하는 불만도( abs(A-B))를 구하라.

 

문제 자체가 직관적이여서 풀이를 떠오르는데는 어렵지 않았는데 구현하는데 어려움을 겪었다.

 

Aclass를 sorting하고 N의 크기가 300000이기 때문에 이분탐색을 이용해서 가장 오차의값이 적은 class를 찾는다.

lower_bound를 이용한후 앞뒤를 확인해 줬다. 근데 이러한 과정에서 v.begin()일때 v.end()일때 v.end()-1일때 3가지경우가 outofbound를 일으킬 수 있어서 이를 예외처리해서 구현했다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;

const ll INF = 100000000000;
const double pi = 3.14159265358979;
const ll MOD = 1000000007;


void yesno(bool isTrue)
{
    if (isTrue)
        cout << "YES\n";
    else
        cout << "NO\n";
}

vector<ll> v;
int N, Q;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    v.resize(N);

    rep(i, N)
    {
        cin >> v[i];
    }

    sort(v.begin(), v.end());

    cin >> Q;

    rep(i, Q)
    {
        ll tmp;
        cin >> tmp;

        auto k = lower_bound(v.begin(), v.end(), tmp);

        ll ans = 1e10;

        if (k == v.begin())
        {
            ans = min(ans, abs(tmp - *k));
            k++;

            if (k == v.end())
            {
                cout << ans << "\n";
                continue;
            }

            ans = min(ans, abs(tmp - *k));
            k--;
        }
        else if (k == v.end())
        {
            k--;
            ans = min(ans, abs(tmp - *k));
        }
        else if (*k == v[N - 1])
        {
            ans = min(ans, abs(tmp - *k));
            k--;
            ans = min(ans, abs(tmp - *k));
            k++;
        }
        else
        {
            ans = min(ans, abs(tmp - *k));
            k--;
            ans = min(ans, abs(tmp - *k));
            k++;
            k++;
            ans = min(ans, abs(tmp - *k));
            k--;
        }

        cout << ans << "\n";
    }

    return 0;

}

 

하지만 해설에서는 더욱 간단한 해결법이 있었다.

바로 인덱스를 1~N까지 잡는것이다. 그럼 계산해도 빼는값이 0이기 때문에 자동적으로 걸러진다.

해설코드는 다음과 같다.

인덱스를 pos1로 잡아놓고 양끝처리를 다음과 같이 해줬다. 이것이 훨씬 깔끔해보인다.

for (int i = 1; i <= Q; i++) {
		int pos1 = lower_bound(A + 1, A + N + 1, B[i]) - A;
		int Diff1 = INF, Diff2 = INF;
		if (pos1 <= N) Diff1 = abs(B[i] - A[pos1]);
		if (pos1 >= 2) Diff2 = abs(B[i] - A[pos1 - 1]);
		cout << min(Diff1, Diff2) << endl;
	}