AC过了11个,可能二分查找插入点的部分写的有问题,调试的实在有点头疼。主要思想是二分法寻找插入点,插入到pos位置之后,能影响到的只会是pos-m到pos+m范围内的数据,所以只检查这段之内是否满足条件即可同时注意边界判断。
#include <bits/stdc++.h>
using namespace std;
int Find(vector<int>list,int start,int end,int x){
int mid;
while(start<end){
mid = start + (end - start) / 2;
if (x == list[mid])
return mid;
if(list[mid]<x)
start=mid+1;
else if(list[mid]>x)
end=mid;
else return mid;
}
if(list[mid]<x)
return mid+1;
else
return mid;
}
int main(){
int n,m,k,mid;
scanf("%d %d %d",&n,&m,&k);
vector<int>list(n);
for(int i=0;i<n;i++)
scanf("%d",&list[i]);
sort(list.begin(),list.begin()+m);
if(list[m-1]-list[0]<=k){
printf("%d",m);
return 0;
}
for(int i=m;i<n;i++){
int pos=Find(list,0,i-1,list[i]);
list.insert(list.begin()+pos,list[i]);
list.erase(list.begin()+i);
int end = (pos < i - m) ? pos : i - m;
for (int j = (pos - m>0) ? (pos - m) : 0; j<end; j++){
if(list[j+m]-list[j]<=k){
printf("%d",i);
return 0;
}
}
}
printf("impossible");
return 0;
}