双指针
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e5 + 5;
int w[N];
bool cmp(int a, int b) { return a > b; }
void solve() {
int n, l; cin >> n >> l;
for (int i = 1; i <= n; i++)cin >> w[i];
sort(w + 1, w + n + 1, cmp);
int res = 0;
for (int h = 1, j = n; h <= n; h++) {
while (j && w[j] < h)j--;//找到左边第一个>=h的位置在j
if (w[h] >= h - 1 && h - j <= l)res = h;//当前第h篇文章>=h-1
}
cout << res << endl;
}
signed main() {
cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}
二分
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e5 + 5;
int w[N];
int n, L;
bool cmp(int a, int b) { return a > b; }
//二分枚举h篇可以满足
int binary() {
int l = 1, r = n;
while (l < r) {
int mid = l + r + 1 >> 1;
//该篇的前L篇要>=h 该篇要>=mid-1,这样子才能用L篇补上
if (w[max(1ll,(mid - L))] >= mid && w[mid] >= mid - 1)l = mid;
else r = mid - 1;
}
return l;
}
void solve() {
cin >> n >> L;
for (int i = 1; i <= n; i++)cin >> w[i];
sort(w + 1, w + n + 1, cmp);
int ans = binary();
//1 0
//0 这样子的情况特判,引用量和可以增加的都为0
if (ans == 1 && L == 0 && w[1] == 0)ans = 0;
cout << ans << endl;
}
signed main() {
cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}