江苏省赛 JSCPC2018 A. Easy h-index

题目

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 a0,a1,a2,…,an which means Bobo has published ai papers with citations exactly i, ﬁnd the h-index of Bobo.

Input

The input consists of several test cases and is terminated by end-of-ﬁle. The ﬁrst line of each test case contains an integer n. The second line contains (n+1) integers a0,a1,…,an.

Output

For each test case, print an integer which denotes the result.
Constraint • 1≤ n ≤2·105 • 0≤ ai ≤109 • 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即可

总结

当时比赛做的时候，觉得很简单，自己的测试用例都是对的，理解也毫无问题，但就是WR，当看到题解时，内心时崩溃的
让求最大的h，这个h是：bobo发表了至少h篇包含h个引语的文章
我们之前的理解是只能是a[i]>=h && i>=h
题解是sum(a[i])>=h

代码

#include <cstdio>

const int N = 200001;

int a[N];

int main()
{
    int n;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i <= n; ++ i) {
            scanf("%d", a + i);
        }
        int h = n + 1;
        long long cnt = 0;
        while (cnt < h) {
            cnt += a[-- h];
        }
        printf("%d\n", h);
    }

}

一个便于理解的代码

#include <bits/stdc++.h>

const int N = 200001;

int n, a[N];

bool check(int h)
{
    long long cnt = 0;
    for (int i = h; i <= n; ++ i) {
        cnt += a[i];
    }
    return cnt >= h;
}

int main()
{
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i <= n; ++ i) {
            scanf("%d", a + i);
        }
        int h = n;
        while (!check(h)) {
            h --;
        }
        printf("%d\n", h);
    }
}