题解 | #空调遥控#
空调遥控
https://www.nowcoder.com/practice/7cb58d56b30c4280ac07ae4428022e03
滑动窗口
先把诉求温度排好序。
再用双指针维护一段人：只要这段里最大值-最小值<=2p就合法，超了就右移左指针。
一路扫过去，记录合法段的最大长度，也就是ans。
void solve(){
int n,p;cin>>n>>p;
vi a(n);
for(int i=0;i<n;++i){
cin>>a[i];
}
sort(all(a));
int ans=0;
for(int i=0,j=0;i<n;++i){
while(j<=i&&a[i]-a[j]>2*p){
++j;
}
ans=max(ans,i-j+1);
}
cout<<ans<<endl;
}
import sys
def solve():
it=iter(map(int,sys.stdin.buffer.read().split()))
n,p=next(it),next(it)
a=[next(it)for _ in range(n)]
a.sort()
ans=0
j=0
for i in range(n):
while j<=i and a[i]-a[j]>2*p:
j+=1
ans=max(ans,i-j+1)
print(ans)
if __name__=='__main__':
solve()
二分
依旧先把诉求温度排个序。 然后二分“最多能满足多少人”这个答案m，检查m是否可行时，就看有没有一个长度为m的连续段满足最大值-最小值<=2p，有就说明这 m个人能被同一个K同时照顾。
void solve(){
int n,p;cin>>n>>p;
vi a(n);
for(int i=0;i<n;++i){
cin>>a[i];
}
sort(all(a));
auto ac=[&](int m)->bool{
for(int i=m-1;i<n;++i){
if(a[i]-a[i-m+1]<=2*p){
return 1;
}
}
return 0;
};
int l=1,r=n,ans=0;
while(l<=r){
int m=(l+r)>>1;
if(ac(m)){
ans=m;
l=m+1;
}else{
r=m-1;
}
}
cout<<ans<<endl;
}
import sys
def solve():
it=iter(map(int,sys.stdin.buffer.read().split()))
n,p=next(it),next(it)
a=[next(it)for _ in range(n)]
a.sort()
def ac(m):
s=m-1
for i in range(s,n):
if a[i]-a[i-s]<=2*p:
return True
return False
l,r,ans=1,n,0
while l<=r:
m=(l+r)>>1
if ac(m):
ans=m
l=m+1
else:
r=m-1
print(ans)
if __name__=='__main__':
solve()
天翼支付科技有限公司公司福利 19人发布
查看6道真题和解析