Killer Problem

Killer Problem

You are given an array of N integers and Q queries. Each query is a closed interval [l, r]. You shouldfind 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<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。