【区间查询】Crawling in process

传送门:这里

Given an array with n integers, and you are given two indices i and j (i ≠ j) in the array. You have to find two integers in the range whose difference is minimum. You have to print this value. The array is indexed from 0 to n-1.

Input

Input starts with an integer T (≤ 5), denoting the number of test cases.

Each case contains two integers n (2 ≤ n ≤ 105) and q (1 ≤ q ≤ 10000). The next line contains n space separated integers which form the array. These integers range in [1, 1000].

Each of the next q lines contains two integers i and j (0 ≤ i < j < n).

Output

For each test case, print the case number in a line. Then for each query, print the desired result.

Sample Input
2
5 3
10 2 3 12 7
0 2
0 4
2 4
2 1
1 2
0 1
Sample Output
Case 1:
1
1
4
Case 2:
1
求区间最小差值
AC代码:
#include <bits/stdc++.h>
using namespace std;
int arr[100000];
int count_num[100000];
inline void getmin(int L, int R)
{
  memset(count_num, 0, sizeof(count_num));
  for (int i = L; i <= R; i++)
    count_num[arr[i]]++;
  int k = -1, ans = 1000;
  for (int i = 1; i <= 1000; i++) {
    if (count_num[i] > 1) {
      ans = 0; break;
    }
    if (count_num[i]) {
      if (k != -1 && i - k < ans)
        ans = i - k;
      k = i;
    }
  }
  printf("%d\n", ans);
}
int main()
{
  int t = 0;
  cin >> t;
  int cas = 0;
  while (t--)
  {
    int n, m, p, q;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
      cin >> arr[i];
    printf("Case %d:\n", ++cas);
    for (int j = 1; j <= m; j++)
    {
      cin >> p >> q;
      getmin(p, q);
    }
  }
  return 0;
}

 

发表评论

电子邮件地址不会被公开。