空调遥控【牛客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,Kp][K−p,Kp]初始化双指针L 0 、 R 0 L0、R0L0、R0维护窗口内元素差值≤ 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的规模无冗余计算。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N5e510;constll mod1e47;constll INF1e18;intmain(){ll n,p;cinnp;vectorllv(n);for(ll i0;in;i)cinv[i];sort(v.begin(),v.end());ll ans1;ll res1;ll l0,r0;while(rn){while(v[r]-v[l]2*p){l;ans--;}if(ansres)resans;r;ans;}coutresendl;return0;}