这个题直接写很难(对我来说😃),我们选择分成两个部分来写:
第一部分:写出求h指数,这有个题刚好考察这个 H 指数
第二部分:再考虑给h-1加一得到更大的h
第一部分:求h指数
h指数:数列中至少含有 H 个数大于等于 H,满足上面条件的最大数
eg
:(1 100 3 3) 则 h 指数将会是 3; (8 3 5 2 10)则 h 指数将会是3; (12 5 6 7 1 9 6)则 h 指数将会是5;
方法:向将其从大到小排序,而后通过越来越满足cnt(x)<x
这个趋势写出二分
我们先将其排序得到一个从大到小的序列,(12 5 6 7 1 9 6) 变为(12 9 7 6 6 5 1)
我们设cnt(x)
: 排序完的序列中,x前面(包括x)所有大于等于x的数的数量
遍历x,发现cnt(x)
先是小于x,而后等于x,最后大于x,譬如,(12 9 7 6 6 5 1)
cnt(12)
=1<12,有1个数大于等于12,小于12(它本身),不满足条件
cnt(9)
=2<9,有2个数大于等于9,小于9(它本身),不满足条件
cnt(7)
=3 <7,有3个数大于等于,小于9(它本身),不满足条件
cnt(6)
=4<6,....
cnt(6)
=5<6,....
cnt(5)
=6>5,有6个数大于等于5,大于5(它本身),满足条件
cnt(1)
=7>1,有7个数大于等于1,大于1(它本身),满足条件
从上面我们知道要二分条件是:如果check()是mid满足右边条件就返回true,也就是满足cnt(mid)>=x
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N];
bool check(int h) {
int cnt = 0;//用来计数h前(包括h)大于等于h的数字
for (int i = 0; i <= h; ++i) {
if (a[i] >= h) {
cnt++;
}
}
return cnt >= h;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a, a + n, greater<int>());
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 << endl;
return 0;
}
第二部分:考虑给h-1加一得到更大的h
直接看代码!
我们多加了个变量more 用来计数h前等于h-1的数字数量,cnt + min(more, L) >= h;
中 min(more, L)的意思是
- 如果L<more,也就是没有足够大的L来给等于h-1的数补一,能补多少补多,那么结果就是L,
- 如果L>more,也就是L比较大,等于h-1的数消耗不完,那么就有多少补多少,那么结果就是more
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 100010;
int a[N];
bool check(int h,int L)
{
int cnt = 0, more = 0; // 用来计数h前等于h-1的数字数量
for (int i = 0; i <= h; ++i)
{
if (a[i] == h - 1)
more++;
if (a[i] >= h)
{
cnt++;
}
}
return cnt + min(more, L) >= h;
}
int main()
{
int n, L;
cin >> n >> L;
for (int i = 0; i < n; ++i)
{
cin >> a[i];
}
sort(a, a + n, greater<int>());
int l = 0, r = n;
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (check(mid, L))
{
l = mid;
}
else
{
r = mid - 1;
}
}
cout << l << endl;
return 0;
}