当前位置：网站首页>hdu5289(Assignment)

hdu5289(Assignment)

2022-07-27 10:14:00 【51CTO】

Description

Tom owns a company and he is the boss. There are n staffs which are numbered from 1 to n in this company, and every staff has a ability. Now, Tom is going to assign a special task to some staffs who were in the same group. In a group, the difference of the ability of any two staff is less than k, and their numbers are continuous. Tom want to know the number of groups like this.

Input

In the first line a number T indicates the number of test cases. Then for each case the first line contain 2 numbers n, k (1<=n<=100000, 0<k<=10^9),indicate the company has n persons, k means the maximum difference between abilities of staff in a group is less than k. The second line contains n integers:a[1],a[2],…,a[n](0<=a[i]<=10^9),indicate the i-th staff’s ability.

Output

For each test,output the number of groups.

Sample Input

       
       2
       
2
       
1 2 4
       
5
       
3 4 5 2 1 6 7 8 9
      






Sample Output

The question ： Given a sequence of positive integers , Ask how many consecutive subsequences there are , The difference between the maximum value and the minimum value is less than k？

Answer key ： Magical monotonous queue , Maintain minimum and maximum values with a monotonically increasing and decreasing queue , Use two front and rear pointers , The front pointer points to the left endpoint of the current interval , The back pointer points to the current element . If new elements are currently added ,max-min>=k, Then it is at least different from the new elements k All elements before that element of will be invalidated , That is out of the team . The answer of each operation is added with the maximum distance that the new element can extend to the left .

Example ：n=6,k=3, The sequence is 5 3 5 2 3 4.q1 Increase the queue for monotony ,q2 Reduce the queue for monotonicity .

       
       step1 : 
       
q1 : 5  
       
q2 : 5
       
l = 0, r = 0
       
ans = 1
       
step2 : 
       
q1 : 3
       
q2 : 5 3
       
l = 0, r = 1
       
ans = 1 + 2
       
step3 : 
       
q1 : 3 5
       
q2 : 5
       
l = 0, r = 2
       
ans = 1 + 2 + 3
       
step4 : 
       
q1 : 2
       
q2 : 5 2
       
l = 0, r = 3
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.

At this time, I found out q1 Medium minimum and q2 The difference between the maximum values in 3>=k, Then start out .

       
       q1 : 2
       
q2 : 2
       
l = 3, r = 3
       
ans = 1 + 2 + 3 + 1
       
step5 : 
       
q1 : 2 3
       
q2 : 3
       
l = 3, r = 4
       
ans = 1 + 2 + 3 + 1 + 2
       
step6 : 
       
q1 : 2 3 4
       
q2 : 4
       
l = 3, r = 5
       
ans = 1 + 2 + 3 + 1 + 2 + 3
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.

So the final answer is 12

       
       #include <iostream>
       
       #include <sstream>
       
       #include <fstream>
       
       #include <string>
       
       #include <map>
       
       #include <vector>
       
       #include <list>
       
       #include <set>
       
       #include <stack>
       
       #include <queue>
       
       #include <deque>
       
       #include <algorithm>
       
       #include <functional>
       
       #include <iomanip>
       
       #include <limits>
       
       #include <new>
       
       #include <utility>
       
       #include <iterator>
       
       #include <cstdio>
       
       #include <cstdlib>
       
       #include <cstring>
       
       #include <cctype>
       
       #include <cmath>
       
       #include <ctime>
       
       using 
       
       namespace 
       
       std;
       
       int 
       
       a[
       
       100010];
       
       deque
       
       <
       
       int
       
       > 
       
       q1, 
       
       q2;
       
       int 
       
       main()
       
{
       
       int 
       
       T;
       
       cin 
       
       >> 
       
       T;
       
       while (
       
       T
       
       --)
       
    {
       
       int 
       
       n, 
       
       k;
       
       cin 
       
       >> 
       
       n 
       
       >> 
       
       k;
       
       for (
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       n; 
       
       ++
       
       i)
       
       scanf(
       
       "%d", 
       
       &
       
       a[
       
       i]);
       
       q1.
       
       clear();
       
       q2.
       
       clear();
       
       int 
       
       l 
       
       = 
       
       0, 
       
       r 
       
       = 
       
       0;
       
       long 
       
       long 
       
       ans 
       
       = 
       
       0;
       
       while (
       
       r 
       
       < 
       
       n)
       
        {
       
       while (
       
       !
       
       q1.
       
       empty() 
       
       && 
       
       q1.
       
       back() 
       
       > 
       
       a[
       
       r])
       
       q1.
       
       pop_back();
       
       q1.
       
       push_back(
       
       a[
       
       r]);
       
       while (
       
       !
       
       q2.
       
       empty() 
       
       && 
       
       q2.
       
       back() 
       
       < 
       
       a[
       
       r])
       
       q2.
       
       pop_back();
       
       q2.
       
       push_back(
       
       a[
       
       r]);
       
       while (
       
       !
       
       q1.
       
       empty() 
       
       && 
       
       !
       
       q2.
       
       empty() 
       
       && 
       
       q2.
       
       front() 
       
       - 
       
       q1.
       
       front() 
       
       >= 
       
       k)
       
            {
       
       if (
       
       q1.
       
       front() 
       
       == 
       
       a[
       
       l])
       
       q1.
       
       pop_front();
       
       if (
       
       q2.
       
       front() 
       
       == 
       
       a[
       
       l])
       
       q2.
       
       pop_front();
       
       l
       
       ++;
       
            }
       
       ans 
       
       += 
       
       r 
       
       - 
       
       l 
       
       + 
       
       1;
       
       r
       
       ++;
       
        }
       
       cout 
       
       << 
       
       ans 
       
       << 
       
       endl;
       
    }
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/208/202207270953077513.html

当前位置：网站首页>hdu5289(Assignment)

hdu5289(Assignment)

边栏推荐

猜你喜欢

随机推荐