关于思路
码风清奇,不用注释。
二分h,对大于等于h的数不用加,加了还是大于。对小于h的数加或许会对答案有增益。最后判断个数。
sort函数降序排序。
check函数中的二分用来查找小于h的最大的数的位置。
然后L个数+1,当然注意边界,不要越界。
如果当前这个+的数已经比h小2了,说明后面的数也不会比h小1,也就对答案没有增益,直接break。
关于用到双指针思想
在我们二分h的时候,就相当于用一个指针指在已经排好序并且是降序的数组的小于h的数的这个位置了,而之后对L个数进行+1,也相当于用一个指针去遍历数组的部分元素。
前一个指针之前的都对答案有增益,后一个指针去遍历,从而找到可能的对答案有增益的数量。
遇事不决,画图解决
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N];int n,L;
bool cmp(int x,int y){
return x>y;
}
bool check(int h){
int cnt=0;
int l=0,r=n+1;
while(l+1<r){
int m=(l+r)>>1;
if(a[m]>=h)l=m;
else r=m;
}
cnt+=l;
for(int i=r;i<=min(n,r+L-1);i++){
if(a[i]+1>=h)cnt++;
if(h-a[i]>=2)break;
}
return cnt>=h;
}
int main(){
cin>>n>>L;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+1+n,cmp);
int l=0,r=N+1;
while(l+1<r){
int mid=(l+r)>>1;
if(check(mid))l=mid;
else r=mid;
}
cout<<l<<endl;
return 0;
}