[nowcoder]青蛙

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #define M 300010
 5 using namespace std;
 6 int n,m,ans,d,T;
 7 int fa[M],a[M],maxn[M];
 8 bool vis[M];
 9 inline int read() {
10     char c = getchar() ; int x = 0 , w = 1 ;
11     while(c>‘9‘||c<‘0‘) { if(c==‘-‘) w = -1 ; c = getchar() ; }
12     while(c>=‘0‘&&c<=‘9‘) { x = x*10+c-‘0‘ ; c = getchar() ; }
13     return x*w ;
14 }
15 int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
16 int main()
17 {
18     //freopen("tt.in","r",stdin);
19     scanf("%d",&T);
20     while(T--)
21     {
22         memset(vis,false,sizeof(vis));
23         ans=0;
24         scanf("%d%d%d",&n,&m,&d);
25         for(int i=1;i<=m+2;i++)
26         {
27             a[i]=read();
28             fa[i]=i;
29         }
30         maxn[0]=1;
31         for(int i=1;i<=m+1;i++)
32         {
33             maxn[i]=maxn[i-1];
34             while(a[maxn[i]+1]-a[i]<=d&&maxn[i]<=m) maxn[i]++;
35         }
36         for(int i=1;i<=maxn[1];i++) vis[i]=true;
37         for(int i=1;i<=m+1;i++)
38         {
39             if(!vis[i]) continue;
40             int MX=find(maxn[i]);
41             if(MX<=i) continue;
42             if(MX<=0) continue;
43             if(!vis[MX])
44             {
45                 vis[i]=false;
46                 vis[MX]=true;
47                 fa[MX]=fa[MX-1];
48             }
49         }
50         for(int i=2;i<=m+1;i++)
51             if(vis[i]&&a[i]+d>=a[m+2])
52                 ans++;
53         printf("%d\n",ans);
54     }
55     return 0;
56 }