蓝桥杯集训·每日一题2024 （二分，双指针）

前言：

  开学了，平时学习的压力也逐渐大起来了，不过还算可以接受，等到后面阶段考的时候就不一样了，我目前为了转专业退选了很多课，这些课我都需要花时间来刷绩点，不然保研就没有竞争力了。我自己会尽量规划好不同板块的学习时间的，所以未来博客我会尽量在闲暇时刻写的。

例题：

两种做法：

1.二分：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+9;
int a[N];
int n,m;
bool check(int mid){
	int c=0,b=0;
	for(int i=1;i<=n;i++){
		if(a[i]>=mid)c++;
		if(a[i]==mid-1)b++;
	}
	return c+min(m,b)>=mid;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int l=1,r=n;
	while(l<r){
		int mid=(l+r+1)/2;
		if(check(mid))l=mid;
		else r=mid-1;
	}
	cout<<r<<endl;
	return 0;
}

对答案进行二分。

2.双指针：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, L;
int w[N];

int main()
{
    scanf("%d%d", &n, &L);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

    sort(w + 1, w + n + 1, greater<int>());

    int res = 0;
    for (int i = 1, j = n; i <= n; i ++ )
    {
        while (j && w[j] < i) j -- ;
        if (w[i] >= i - 1 && i - j <= L)
            res = i;
    }

    printf("%d\n", res);
    return 0;
}

看别人的题解知道的做法，就是用对撞指针来找>=l和=l-1的数的个数。