喜欢就点个赞👍吧,每天都会更新哦~^-^
双指针 (牛的学术圈I)
Problem:
给定一个n,k,表示有n个数,找到 h 指数 h,ℎ 指数等于使得研究员有至少 ℎ 篇引用次数不少于 ℎ 的论文的最大整数 ℎ。如果k!=0,则每个数最多可以变大1,但是不能有超过k个数同时变大1
Ideas:
sort + 双指针:
数组不动,先当前数组位置下的最大的h指数,然后数组移动,继续往前找更大的h指数即可,详解看代码描述
二分 + 遍历:
先找到一个合适的h然后去判断使用后满不满足h指数的条件
单纯双指针:
根据数据范围来看,数据范围在1~1e5,那么可以用一个数组存储所有的数的个数,然后通过双指针从1到出现的最大值依次遍历,达到o(n)时间复杂度,具体看代码解析
Code:
sort + 双指针
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
signed main()
{
int n, k;
cin >> n >> k;
int a[N];
map<int, int> mp; // 存储出现次数
for(int i = 0; i < n; i ++ ) {
cin >> a[i];
mp[a[i]] ++ ;
}
sort(a, a + n);
int res = 0;
int j = 0;
for(int i = 0; i < n; i ++ ) {
while(j <= n && a[i] >= j && n - i >= j) {
res = max(res, j);
j ++ ;
}
}
j = 0;
for(int i = 0; i < n; i ++ ) {
while(j <= n && a[i] >= j - 1 && n - i - mp[a[i]] + min(mp[a[i]], k) >= j) {
res = max(res, j);
j ++ ;
}
}
cout << res << endl;
}
二分
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int n, q;
int a[N];
bool check(int mid) {
int x = q;
int res = 0;
for(int i = 0; i < n; i ++ ) {
if(a[i] >= mid) res ++ ;
if(a[i] == mid - 1 && x > 0) {
x -- ;
res ++ ;
}
}
if(res >= mid) return 1;
return 0;
}
signed main()
{
cin >> n >> q;
for(int i = 0; i < n; i ++ ) cin >> a[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 << endl;
}
双指针:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
signed main()
{
int n, k;
cin >> n >> k;
int a[N]; // 存取每个数的个数
int ma = 0;
for(int i = 1; i <= n; i ++ ) {
int x;
cin >> x;
a[x] ++ ;
ma = max(ma, x); // 记录最大值
}
int res = 0; // 最终结果
int sum = n; // 初始化,目前大于0的个数肯定是所有数量
int j = 0;
for(int i = 0; i <= ma + 5; i ++ ) { // ma + 5 开大保险(展示容错),未处理k
while(sum >= j && i >= j) { // 双指针的重点,个数要比j多,i要比j大
res = max(res, j); // 成立,h指数可以为j
j ++ ;
}
sum -= a[i]; // 总数减
if(sum + min(a[i], k) >= j && i >= j - 1 && k != 0) res = max(res, j); // 处理k
}
cout << res << endl;
}