C++14(g++5.4) 解法, 执行用时: 248ms, 内存消耗: 30404K, 提交时间: 2020-08-05 10:50:43

#include<bits/stdc++.h>
#pragma GCC optimize(3,"Ofast","inline")
#define Fox ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int N=3e5+10;
const int mod=1e9+7;
int T,n,m,d,a[N];
int main(){
	Fox;
	cin>>T;
	while(T--){
		cin>>n>>m>>d;
		m+=2;
		for(int i=1;i<=m;i++)cin>>a[i];
		int r=1,ans=N;
		for(int i=1;i<=m && r<=m;i++){
			while(r<=m && a[r]-a[i]<=d)r++;
			ans=min(ans,r-i-1);
		}
		cout<<ans<<"\n";
	}
	return 0;
}

pypy3 解法, 执行用时: 1505ms, 内存消耗: 114944K, 提交时间: 2022-07-11 13:11:25

from sys import stdin
input = stdin.readline
for i in range(int(input())):
    n,m,d = map(int,input().split())
    s = list(map(int,input().split()))
    f = [0] 
    for i in s:
        f.append(i)
    l  = 1
    ans = 1e9 + 1
    m +=2
    for i in range(1,m + 1):
        while l <= m and f[l] - f[i] <= d:
            l += 1
        ans = min(ans ,l - i - 1)
        if l == m + 1:
            break
    print(ans)

C++(clang++ 11.0.1) 解法, 执行用时: 930ms, 内存消耗: 1476K, 提交时间: 2023-02-02 00:11:34

#include<bits/stdc++.h>
using namespace std;
int a[310000];
int main()
{
	int t,n,m,d;
	cin>>t;
	while(t--){
		cin>>n>>m>>d;
		m+=2;
		for(int i=1;i<=m;i++)
		cin>>a[i];
		int wei=1,ret=0x3f3f3f3f;
		for(int i=1;i<=m;i++){
			if(wei==m+1)
			break;
			while(wei<=m&&a[wei]-a[i]<=d)
			wei++;
			ret=min(ret,wei-i-1);
		}
		cout<<ret<<endl;
	}
    return 0;
}