3745. 牛的学术圈 I(acwing)

标签：3745 论文 mid 次数引用 Bessie 100 acwing 学术

文章目录

3745. 牛的学术圈 I

3745. 牛的学术圈 I

题目描述

由于对计算机科学的热爱，以及有朝一日成为「Bessie 博士」的诱惑，奶牛 Bessie 开始攻读计算机科学博士学位。

经过一段时间的学术研究，她已经发表了 N 篇论文，并且她的第 i 篇论文得到了来自其他研究文献的 ci 次引用。

Bessie 听说学术成就可以用 h 指数来衡量。

h 指数等于使得研究员有至少 h 篇引用次数不少于 h 的论文的最大整数 h。

例如，如果一名研究员有 4 篇论文，引用次数分别为 (1, 100, 2, 3)，则 h 指数为 2；然而若引用次数为 (1, 100, 3, 3) 则 h 指数将会是 3。

为了提升她的 h 指数，Bessie 计划写一篇综述，并引用一些她曾经写过的论文。

由于页数限制，她至多可以在这篇综述中引用 L 篇论文，并且她只能引用每篇她的论文至多一次。

请帮助 Bessie 求出在写完这篇综述后她可以达到的最大 h 指数。

注意：Bessie 的导师可能会告知她纯粹为了提升 h 指数而写综述存在违反学术道德的嫌疑；我们不建议其他学者模仿 Bessie 的行为。

输入格式

输入的第一行包含 N 和 L。
第二行包含 N 个空格分隔的整数 c1,…,cN。

输出格式

输出写完综述后 Bessie 可以达到的最大 h 指数。

数据范围

1 ≤ N ≤ 10⁵
0 ≤ ci ≤ 10⁵
0 ≤ L ≤ 10⁵

输入样例1：

4 0
1 100 2 3

输出样例1：

样例1解释：
Bessie 不能引用任何她曾经写过的论文。上文中提到，(1, 100, 2, 3) 的 h 指数为 2。

输入样例2：

4 1
1 100 2 3

输出样例2：

样例2解释：
如果 Bessie 引用她的第三篇论文，引用数会变为 (1, 100, 3, 3)。上文中提到，这一引用数的 h 指数为 3。

h指数的解释与计算

h指数（h-index）是一种用来衡量一个研究员学术影响力的指标，特别是用来量化其科研成果的引用情况。计算h指数的步骤相对简单直观，以下是其基本计算流程：

收集论文及引用数：首先，收集该研究员所有学术论文的引用次数。
引用数排序：将这些论文按照引用次数从高到低进行排序。
确定h指数：从列表的顶端开始，向下检查，直到找到一个位置 N，使得排在这个位置的论文的引用次数小于或等于位置数字（即N）时停止。此时，N就是h指数。换句话说，h指数是指一个研究员有h篇论文，每篇被引用了至少h次，而其余的论文引用次数不超过h次。

例子1： 引用次数为 (1,100,2,3)，排序后为 (100,3,2,1)：

第1篇论文引用次数100，至少有1篇论文引用次数不少于1（满足）；
第2篇论文引用次数3，至少有2篇论文引用次数不少于2（满足）；
第3篇论文引用次数2，至少有3篇论文引用次数不少于3（不满足）。

因此，h指数为2。

例子2： 引用次数为 (1,100,3,3)，排序后为 (100,3,3,1)：

第1篇论文引用次数100，至少有1篇论文引用次数不少于1（满足）；
第2篇论文引用次数3，至少有2篇论文引用次数不少于2（满足）；
第3篇论文引用次数3，至少有3篇论文引用次数不少于3（满足）；
第4篇论文引用次数1，至少有4篇论文引用次数不少于4（不满足）。

因此，h指数为3。

h指数试图为研究者的学术影响力和成果的广度及深度提供一个统一的评价标准，它同时考虑了发表论文的数量与论文的学术影响力。

二分查找

// 引入所有标准库的头文件
#include<bits/stdc++.h>
using namespace std;

// 定义一个足够大的常量 z，用于存储论文的引用次数
const int z=1e5+10;

// 定义全局变量，用于存储论文数量和每篇论文的引用次数
int n,k;
int c[z];

// 定义一个辅助函数 check，用于判断在给定的 h 指数 mid 下，Bessie 是否能够达到或超过这个 h 指数
bool check(int mid)
{
    int a=0,b=0; // a 用于统计引用次数不小于 mid 的论文数量，b 用于统计引用次数为 mid-1 的论文数量
    for(int i=0; i<n; i++) // 遍历所有论文
    {
        if(c[i]>=mid) a++; // 如果论文的引用次数不小于 mid，则 a 增加
        if(c[i]==mid-1) b++; // 如果论文的引用次数恰好为 mid-1，则 b 增加
    }
    // 如果 a 加上 b 的最小值（考虑 k 的限制）不小于 mid，则返回 true，表示可以达到或超过 h 指数
    if((a+min(b,k))>=mid) return true;
    // 否则返回 false，表示无法达到或超过 h 指数
    return false;
}

// 主函数
int main()
{
    // 读取论文数量 n 和 Bessie 可以引用的论文数量 k
    cin>>n>>k;
    // 读取每篇论文的引用次数
    for(int i=0; i<n; i++)
        cin>>c[i];
    // 初始化二分查找的左右边界
    int l=0,r=n;
    // 进行二分查找——右查找，查找最大值
    while(l<r)
    {
        // 计算二分查找的中间值 mid
        int mid=(l+r+1)>>1;// 注意这里的 mid 计算方式是 (l + r + 1) / 2，防止溢出
        // 如果当前的 h 指数 mid 满足条件，则左边界更新为 mid
        if(check(mid)) l=mid;
        // 否则右边界更新为 mid - 1
        else r=mid-1;
    }
    // 输出最终找到的最大的 h 指数
    cout<<r<<endl;
    // 程序结束
    return 0;
}

这段代码通过二分查找算法来找到 Bessie 在写完综述后可以达到的最大 h 指数。二分查找的时间复杂度为 O(log n)，其中 n 是论文的数量。代码首先读取输入的论文数量和可以引用的论文数量，然后读取每篇论文的引用次数。接着，通过二分查找确定最大的 h 值，使得至少有 h 篇论文的引用次数不小于这个 h 值。最后，输出这个 h 值作为结果。

需要注意的是，代码中的 const int z=1e5+10; 定义了一个非常大的数，这是为了确保数组 c 有足够的空间来存储所有可能的引用次数。在实际应用中，这个值可以根据实际情况进行调整。此外，二分查找中的 mid 计算方式 (l + r + 1) / 2 是为了避免在计算过程中发生整数溢出。

标签：3745,论文,mid,次数,引用,Bessie,100,acwing,学术
From： https://blog.csdn.net/m0_73841621/article/details/136721689

3745. 牛的学术圈 I(acwing)

文章目录