Acowdemia I

题意

Bessie 有 N 篇论文，第 i 篇论文当前有 c_i 次引用。

她最多可以在综述中引用 L 篇自己的论文，每篇论文最多被引用一次，也就是最多给这些论文各加 1 次引用。

求修改后能达到的最大 h-index。

思路

暴力想法

最直接的想法是枚举每篇论文是否被综述引用：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 13:24
 * update_at: 2026-07-11 13:28
 */
// brute.cpp：小数据暴力解，使用 01 序列递归枚举每篇论文是否被综述引用。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20;

int n, L;
int citation[MAXN];
int choose_paper[MAXN]; // choose_paper[i] 表示第 i 篇论文是否被额外引用。
int ans;

int calc_h_index() {
    int temp[MAXN];
    for (int i = 1; i <= n; i++) {
        temp[i] = citation[i] + choose_paper[i];
    }

    sort(temp + 1, temp + n + 1, greater<int>());

    int h = 0;
    for (int i = 1; i <= n; i++) {
        if (temp[i] >= i) {
            h = i;
        }
    }
    return h;
}

bool check_limit() {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (choose_paper[i] == 1) {
            cnt++;
        }
    }
    return cnt <= L;
}

void dfs(int dep) {
    if (dep == n + 1) {
        if (check_limit()) {
            int now = calc_h_index();
            if (ans < now) {
                ans = now;
            }
        }
        return;
    }

    // 这一层决定第 dep 篇论文是否被综述引用。
    choose_paper[dep] = 0;
    dfs(dep + 1);

    choose_paper[dep] = 1;
    dfs(dep + 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> L;
    for (int i = 1; i <= n; i++) {
        cin >> citation[i];
    }

    ans = 0;
    dfs(1);

    cout << ans << '\n';

    return 0;
}

这个暴力把问题看成一串 01 选择：choose_paper[i] = 0/1 表示第 i 篇论文不引用或引用。递归生成完整选择后，检查引用数量是否不超过 L，再计算当前 h-index。

这种写法适合小数据，但满数据下有 $2^N$ 种选择，无法通过。

只判断 `h+1`

官方解析的关键结论是：最终 h-index 最多只会比当前 h-index 多 1。

原因是每篇论文最多只能增加 1 次引用。若当前 h-index 是 h，那么第 h+1 高引用的论文原本最多只有 h 次引用，综述后最多也只能到 h+1。

所以答案只可能是：

text

1h 或 h+1

先把引用次数从大到小排序，求出当前 h-index。然后设 $target = h + 1$ 。

为了达到 target，需要至少 target 篇论文引用次数不少于 target：

已经不少于 target 的论文，记为 already_ok；
还差 1 次，也就是引用次数为 target - 1 的论文，记为 can_add；
还缺的达标论文数是 $need = target - already_ok$ 。

如果 $need <= L$ 且 $need <= can_add$ ，就能把这些差 1 次的论文各引用一次，答案变成 target。否则答案仍是 h。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 13:24
 * update_at: 2026-07-11 13:28
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n, L;
int citation[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> L;
    for (int i = 1; i <= n; i++) {
        cin >> citation[i];
    }

    sort(citation + 1, citation + n + 1, greater<int>());

    int h = 0;
    for (int i = 1; i <= n; i++) {
        if (citation[i] >= i) {
            h = i;
        }
    }

    int target = h + 1;
    if (target <= n) {
        int already_ok = 0; // 已经达到 target 次引用的论文数。
        int can_add = 0;    // 加 1 次引用后能达到 target 的论文数。

        for (int i = 1; i <= n; i++) {
            if (citation[i] >= target) {
                already_ok++;
            } else if (citation[i] + 1 >= target) {
                can_add++;
            }
        }

        int need = target - already_ok;
        if (need <= L && need <= can_add) {
            h = target;
        }
    }

    cout << h << '\n';

    return 0;
}

复杂度

排序复杂度为 $O(N \log N)$ ，之后线性扫描，整体时间复杂度为 $O(N \log N)$ 。

空间复杂度为 $O(N)$ 。

总结

这题的核心不是枚举引用方案，而是先看清每篇论文最多只会增加 1 次引用。

这个限制让 h-index 最多提升 1，于是问题从“选择哪些论文”变成了“判断 h+1 是否可达”。

目录

题意

思路

暴力想法

只判断 h+1

代码

复杂度

总结

只判断 `h+1`