C.现在是，学术时间 (I)
题意
- 每个教授i有1篇引用量为\(a_i\)的论文，求将论文重新分配后的最大H指数和
一位教授的H指数为使得"该教授发表的所有论文中，有至少H篇论文的引用量大于等于H"这一命题成立的最大的H。
思路1
- 如果不对论文进行分配，那么每篇被引用数量不为0的论文对H指数和的贡献都为1，最大H指数和为被引用数量不为0的论文数
- 由于最大H指数和不可能大于被引用数量不为0的论文数，因此不进行分配便是最优解
“不要想学术不端，平平淡淡才是真”？？
代码
点击查看代码
#include <bits/stdc++.h>
using i64 = long long;
void solve() {
int n;
std::cin >> n;
int ans = 0;
for (int i = 0; i < n; i++) {
int a;
std::cin >> a;
ans += (a > 0); //如果不为0，答案就+1
}
std::cout << ans << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}
思路2
- 因为论文顺序对原题不产生影响，则可以二分制造出序列的二段性后通过多次二分【每次r不变，因为每篇论文只能使用1次】每次找到符合条件的H指数再求和
代码
点击查看代码
#include<iostream>
using namespace std;
#define prep(i,a,b) for(int i = (a); i <= (b); i ++)
#define rrep(i,a,b) for(int i = (a); i >= (b); i --)
typedef long long LL;
const char nl = '\n';
int T, n, m;
const int N = 1e5 + 10;
int a[N];
bool check(int x){
return a[x] >= n - x + 1;
}
void solve() {
LL ans = 0;
cin >> n;
prep(i,1,n)cin >> a[i];
sort(a + 1,a + n + 1);
int l = 1,r = n;
while(l < r){
int mid = l + r >> 1;
if(check(mid))r = mid;
else l = mid + 1;
}
if(!check(l)){
cout << 0 << nl;
return;
}
else{
ans += (n - l + 1);
while(l > 1){ //当论文没有使用完时
l = 1,r --,n = r; //每次l复原，r--，n = r相当于分成若干个二分问题求总和
while(l < r){
int mid = l + r >> 1;
if(check(mid))r = mid;
else l = mid + 1;
}
if(!check(l))continue;
else ans += (n - l + 1);
}
}
cout << ans << nl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> T;
while (T--) {
solve();
}
return 0;
}