蓝桥杯集训·每日一题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的数的个数。