Killer Problem

You are given an array of N integers and Q queries. Each query is a closed interval [l, r]. You should find the minimum absolute difference between all pairs in that interval.

Input 

First line contains an integer T (T10). T sets follow. Each set begins with an integer N ( N200000). In the next line there are N integers a_i ( 1a_i10⁴), the number in the i-th cell of the array. Next line will contain Q ( Q10⁴). Q lines follow, each containing two integers l_i, r_i ( 1l_i, r_iN, l_i < r_i) describing the beginning and ending of of i-th range. Total number of queries will be less than 15000.

Output 

For the i-th query of each test output the minimum | a_j–a_k| for l_ij, kr_i (jk) a single line.

Sample Input 

1
10
1 2 4 7 11 10 8 5 1 10000
4
1 10
1 2
3 5
8 10

Sample Output 

0
1
3
4

---

題目描述：

詢問區間的絕對值差最小的 pair。

題目解法：

只能蠻幹，將區間所有數字拿出來排序，並且查找任相鄰兩個數字的差。

// 當區間長度大於某一定值時，直接輸出 0。

#include <stdio.h>
#include <algorithm>
using namespace std;
int A[200005], B[200005];
int main() {
    int testcase;
    scanf("%d", &testcase);
    while(testcase--) {
        int n, m;
        int i, j, k, l, r;
        scanf("%d", &n);
        for(i = 1; i <= n; i++)
            scanf("%d", &A[i]);
        scanf("%d", &m);
        while(m--) {
            scanf("%d %d", &l, &r);
            int ret = 0xfffffff;
            if(r - l > 200)    ret = 0;
            else {
                for(i = l, j = 0; i <= r; i++, j++)
                    B[j] = A[i];
                sort(B, B+j);
            }
            for(i = 1; i < j && ret; i++)
                ret = min(ret, B[i] - B[i-1]);
            printf("%d\n", ret);
        }
    }
    return 0;
}

---