HDU 6276 Easy h-index

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

思路：由于应用次数是递增的，于是我们可以从后向前遍历，每次将答案加上a[i]如果答案大于等于i就跳出循环并将i输出；

AC代码：

#include
#include
#include
using namespace std;
 
const int N=200010;
 
int a[N];
 
int main()
{
	int n;
	while(cin>>n)
	{
		for(int i=0;i<=n;i++)
			scanf("%d",&a[i]);
		int res=0;
		for(int i=n;i>=0;i--)
		{
			res+=a[i];
			if(res>=i)
			{
				res=i;
				break;
			}
		}
		printf("%d\n",res);
	}
}