蓝桥集训之牛的学术圈 I
蓝桥集训之牛的学术圈 I
-
核心思想：二分
- 确定指数x后 判断当前c[i]是否>=x(满足条件) 并记录次数
- 同时记录 +1后满足条件的个数
- 最后取bns和m的最小值 为满足条件的元素个数
- ans+bns为当前指数x下 满足条件的元素个数
-
#include <iostream>#include <cstring>#include<algorithm>using namespace std;const int N = 100010;int c[N];int n,m;bool check(int x){int ans=0,bns=0;for(int i=1;i<=n;i++){if(c[i] >= x) ans++;else if(x - c[i] == 1) bns++;}bns = min(m,bns);ans+=bns;return ans>=x;}int main() {cin>>n>>m;for(int i=1;i<=n;i++) cin>>c[i];int l=0,r=N;while(l<r){int mid = l+r+1>>1;if(check(mid)) l = mid;else r = mid-1;}cout<<l;return 0;}