本文共 1339 字，大约阅读时间需要 4 分钟。

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.InputFirst line contains an integer T (T ≤ 10). T sets follow. Each set begins with an integer N (N ≤200000). In the next line there are N integers ai (1 ≤ ai ≤ 104), the number in the i-th cell of thearray. Next line will contain Q (Q ≤ 104). Q lines follow, each containing two integers li, ri (1 ≤ li,ri ≤ N, li < ri) describing the beginning and ending of of i-th range. Total number of queries will beless than 15000.OutputFor the i-th query of each test output the minimum |ajak| for li ≤ j, k ≤ ri (j ̸= k) a single line.Sample Input1101 2 4 7 11 10 8 5 1 1000041 101 23 58 10Sample Output013

4

题目大概：

给出n个数，m条询问。求出l 到r 区间内任意一对数的差绝对值的最小值。

思路：

看了数据量，首先发现，数据的大小比较小。枚举一对对的数一定会超时，所以，可以枚举数的大小。而且数的大小是从最小值枚举到最大值，是排好序的，只需要算相邻的差的绝对值就好了。这样，时间复杂度就降低了不少，好像过很勉强，试一试，过了。

代码：

#include 
   
    using namespace std;const int maxn=2e5+10;const int INF=0x3f3f3f3f;int a[maxn];int b[maxn];int work(int l,int r){    memset(b,0,sizeof(b));    int min_1=INF;    int max_1=0;    for(int i=l;i<=r;i++)    {        if(!b[a[i]])b[a[i]]++;        else return 0;        min_1=min(min_1,a[i]);        max_1=max(max_1,a[i]);    }    int pre=min_1;    //cout<
    
<
   

转载地址：https://blog.csdn.net/a1046765624/article/details/80753052 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！