蓝桥集训之牛的学术圈 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;}