2018湘潭邀请赛A题题解

2018湘潭邀请赛A题题解

做题网址：点击打开链接

下面是原题题目：

A. Easy h-index

The h-index of an author is the largest h where he has at least h papers with citations not less than h.

Bobo has published many papers. Given a₀, a₁, a₂, . . . , a_n which means Bobo has published a_i papers with citations exactly i, find the h-index of Bobo.

 

Input

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains an integer n. The second line contains (n + 1) integers a₀, a₁, . . . , a_n.

 

Output

For each test case, print an integer which denotes the result.

 

Constraint

• 1 n 2 105

• 0 a_i109

• The sum of n does not exceed 250, 000.

 

Sample Input

1

1 2

2

1 2 3

3

0 0 0 0

 

Sample Output

1

2

0

 

 

 

比赛做这道题被英文句子绕得有点晕，幸好被队友及时发现，就很开心地躺了这道题。

 

下面写下这道题大概的意思和思路：

 

先援引下百科上对h-index的解释，H指数(h-index)的计算基于其研究者的论文数量及其论文被引用的次数。赫希认为：一个人在其所有学术文章中有N篇论文分别被引用了至少N次，他的H指数就是N。如美国免疫学家理查德·弗莱奥发表的900篇文章中，有107篇被引用了107次以上，他的H指数是107。

 

然后是对输入数据的解释，输入的n代表他最大的文章被引用次数。接着输入的数组的意思是，数组按a₀, a₁, a₂, . . . , a_n 的顺序输入的，其中i是被引用次数，a[i]是被引用过i次的文章数。

 

题目意思差不多理清了，所以我们只要倒着遍历数组从n-1开始，使a[i] = a[i]+a[i+1]即可。我们就能得到每个被引用次数对应的小于等于它的文章数量。完成后顺序遍历，每次答案取i，当文章数量小于被引用次数时中断并输出结果。

 

 

下面是我的AC代码：

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int SIZE = 2e5+5;
long long arr[SIZE];
int main() {
    int n;
    while(scanf("%d", &n) != EOF) {
        for(int i = 0; i <= n; i++) {
            scanf("%lld", &arr[i]);
        }
        for(int i = n-1; i >= 0; i--) {
            arr[i] += arr[i+1];
        }
        int ans = 0;
        for(int i = 0; i <= n && arr[i] >= i; i++) {
            ans = i;
        }
        printf("%d\n", ans);
    }
    return 0;
}