空调遥控【牛客tracker 每日一题】
空调遥控
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
d d dddd作为集训队的队长，一直掌管着集训室的空调遥控器，她需要调整温度使队员们更好地进入训练状态，已知集训室一共有n nn名队员，每位队员都有一个温度诉求a [ i ] ( 1 ≤ i ≤ n ) a[i](1≤i≤n)a[i](1≤i≤n)，当室内温度为K KK时，当且仅当∣ a [ i ] − K ∣ ≤ p ∣a[i]−K∣≤p∣a[i]−K∣≤p时，这个队员能够正常进入训练状态，否则就会开始躁动，作为队长，d d dddd需要调整好温度，她想知道，在最佳情况下，最多有多少队员同时进入训练状态
输入描述：
第一行两个数n , p ( 1 ≤ n , p ≤ 1000000 ) n,p(1≤n,p≤1000000)n,p(1≤n,p≤1000000),含义如题面描述
接下来一行n nn个数a [ i ] ( 1 ≤ a [ i ] ≤ 1000000 ) a[i](1≤a[i]≤1000000)a[i](1≤a[i]≤1000000)表示每个队员的温度诉求
输出描述：
输出一个数字，表示最多有多少队员同时进入训练状态
示例1
输入：
6 2 1 5 3 2 4 6输出：
5说明：
温度调成3 33或4 44，都可以满足5 55名队员同时进入训练状态
解题思路
本题核心是通过排序+滑动窗口（双指针）求解最多满足条件的队员数：首先将队员的温度诉求数组排序，问题等价于找最长子数组，使其最大值与最小值的差≤ 2 p ≤2p≤2p（对应温度区间[ K − p , K + p ] [K-p,K+p][K−p,K+p]）；初始化双指针L = 0 、 R = 0 L=0、R=0L=0、R=0，维护窗口内元素差值≤ 2 p ≤2p≤2p，右指针R RR逐个右移，若v [ R ] − v [ L ] > 2 p v[R]-v[L]>2pv[R]−v[L]>2p则左移L LL缩小窗口，同时记录窗口的最大长度。排序的时间复杂度O ( n log n ) O(n \log n)O(nlogn)，滑动窗口线性遍历O ( n ) O(n)O(n)，整体复杂度适配n ≤ 1 e 6 n≤1e6n≤1e6的规模，精准找到能同时进入训练状态的最多队员数。
总结
- 核心逻辑：将温度诉求排序后，用滑动窗口找差值≤ 2 p ≤2p≤2p的最长子数组，其长度即为答案。
- 关键操作：双指针维护合法窗口，右指针扩展、左指针收缩，动态更新最大窗口长度。
- 效率保障：排序+线性遍历的时间复杂度适配n ≤ 1 e 6 n≤1e6n≤1e6的规模，无冗余计算。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vt;typedefpair<ll,ll>pll;constll N=5e5+10;constll mod=1e4+7;constll INF=1e18;intmain(){ll n,p;cin>>n>>p;vector<ll>v(n);for(ll i=0;i<n;i++)cin>>v[i];sort(v.begin(),v.end());ll ans=1;ll res=1;ll l=0,r=0;while(r<n){while(v[r]-v[l]>2*p){l++;ans--;}if(ans>res)res=ans;r++;ans++;}cout<<res<<endl;return0;}