AcWing 3745. 牛的学术圈 I
原题链接
简单
作者:
DASH156
,
2024-03-16 22:56:49
,
所有人可见
,
阅读 9
二分+贪心
#include <bits/stdc++.h>
using namespace std;
//二分+贪心+二分 -> 满足引用次数大于h的个数考虑
const int N = 100010;
int n, L;
int c[N];
bool check(int m) {
int i;
for (i = 1; i <= m; i++) {
if (c[i] >= m) break;
}
if (n - i + 1 < m) return false;
else return true;
}
int main() {
cin >> n >> L;
for (int i = 1; i <= n; i++) {
cin >> c[i];
}
sort(c + 1, c + n + 1);
int h = 0;
int l = c[1], r = c[n];
int mid = 0;
while (l <= r) {
mid = (l + r) / 2;
if (check(mid)) {
l = mid + 1;
h = mid;
}
else r = mid - 1;
}
cout << h << endl;
for (int i = n; i > 0; i--) {//将不超过h的论文引用一次,且与h的差距越小越优先
if (L == 0) break;
if (c[i] <= h) {
c[i]++;
L--;
}
}
sort(c + 1, c + n + 1);
l = c[1], r = c[n];
while (l <= r) {
mid = (l + r) / 2;
if (check(mid)) {
l = mid + 1;
h = mid;
}
else r = mid - 1;
}
cout << h;
}
双指针
#include <bits/stdc++.h>
using namespace std;
//双指针,两个指针要存在单调关系 -> 从h个数满足的条件考虑
const int N = 100010;
int n, L;
int c[N];
int main() {
cin >> n >> L;
for (int i = 1; i <= n; i++) {
cin >> c[i];
}
sort(c + 1, c + n + 1,greater<int>());//降序排序
//对于h个数来说,其最小数>=h-1,且h-1的数量<=L
int res = 0;
for (int i = 1, j = n; i <= n; i++) {
while (j && c[j] < i) j--;//找到第一个大于等于h的数
if (c[i] >= i - 1 && i - j <= L) res = i;
}
cout << res;
}