2018 ccpc 샹 탄 초청 경기 A. Easy h - index [사고]

3319 단어 사고HDU
Easy h-index
                                                                   Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)                                                                                        Total Submission(s): 259    Accepted Submission(s): 103
Problem Description
경기 제목:
http://acm.hdu.edu.cn/downloads/2018ccpc_hn.pdf
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, 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 
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
 

Source
CCPC2018-湖南全国邀请赛-重现赛(感谢湘潭大学)
 
题目:首先读懂题目,作者的h指数是一个最大的h,h代表至少有h篇文章被引用至少h次。。。

那么只需要求一个前缀和就可以啦。。

代码:

#include
using namespace std;
const int maxn = 2e5+7;
int a[maxn], b[maxn];


int main()
{
    int n;
    //freopen("in.txt", "r", stdin);
    while(~scanf("%d", &n))
    {
        //bool f = true;
        for(int i = 0; i <= n; i++) scanf("%d", &a[i]);
        for(int i = n - 1; i >= 0; i--) a[i] += a[i + 1];
        for(int i = n; i >= 0; i--)
        {
            if(a[i] >= i) {
                printf("%d
", i); //f = false; break; } } //if(f) printf("0
"); } return 0; }

좋은 웹페이지 즐겨찾기