UVa OJ 11898 - Killer Problem

문제 링크

\(N\leq{2\cdot{10^5}}\)

\(1\leq{a_i}\leq{10^4}\)

\(Q\leq{10^4}\)

\(1\leq{l_i},\,{r_i}\leq{N}\) (\(l_i<r_i\))

N을 입력받고 10^4 이하의 정수 \(a_i\) 를 N개 입력받는다.

그리고 쿼리의 수 Q를 입력받는다. 각 쿼리는 l, r을 입력받는데

l~r 사이의(inclusive) 정수들중 차이가 최소값을 출력하는 것이다. 두 수 a,b의 차이라 함은 abs(a-b) 를 말한다.

그렇기 때문에 l~r 에 포함된 수에서 모든 정수 쌍에 대해 최소 차이값을 출력하는 것이다.

처음에 머지소트를 하여 구간의 정렬된수들에 대해 O(N) 으로 순회하며 차이를 구하면서 최소를 취하는 식으로

생각을 했는데 이렇게 하면 각 쿼리마다 O(NlgN) 이 걸리기 때문에 결과적으로 O(NQlgN) 의 시간복잡도가 걸리게 된다.

NQ만해도 20억이 넘으므로 무리일 것이다. 그럼 어떻게 할까? 문제의 조건을 잘 보면 모든 정수는 10000이하의 자연수이다.

그러면 아무리 l,r 에 포함된 수가 커도 비둘기 집의 정리에 의해 r-l+1 이 10000보다 커지는 순간 부터는

같은 수가 적어도 한쌍은 생기기 때문에 쿼리의 답이 무조건 0임을 알 수가 있다. 그러므로 r-l >= 10000 일때는

무조건 0을 출력, 그 외의 경우에는 그냥 직접 정렬을 해서 순회하며 답을 찾으면된다.

그러면 각 쿼리마다 최악의 경우 O(KlgK) (K<=10000) 가 걸리게 된다. 그럼 전체 복잡도는 O(QKlgK) 여서 1억이 좀 넘는다.

좀 애매한 시간이긴한데 실제로 제출해보면 잘 정답처리된다. 매번 순회할 때 같은 수가 나오자마자 종료하고

0을 출력한다던지하는 컷팅을 좀 한다면 약간은 더 빨라질지도 모른다.  하지만 안해도 잘됨.

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
 
int A[200003];
int N, Q, T;
int ans;
int main() {
    scanf("%d", &T);
    while(T--){
        scanf("%d",&N);
        for(int i = 0 ; i < N; i++) scanf("%d",&A[i]);
        scanf("%d",&Q);
        for(int i = 0 ; i < Q; i++) {
            int s, e;
            scanf("%d%d",&s, &e);
            s--,e--;
            if(e-s >= 10000){
                printf("0\n");
                continue;
            }
            ans = INF;
            vector<int> sorted;
            for(int i = s ; i <= e; i++) sorted.push_back(A[i]);
            sort(sorted.begin(), sorted.end());
            for(int i = 0 ; i < sorted.size()-1; i++) ans = min(ans, abs(sorted[i]-sorted[i+1]));
            printf("%d\n",ans);
        }
    }
    return 0;
}