USACO 2017 December Contest, Platinum Problem 3. Greedy Gift Takers

USACO 2017年首轮月赛白金级题3

Greedy Gift Takers

Farmer John's nemesis, Farmer Nhoj, has N cows (1≤ N ≤ 10⁵), conveniently numbered 1... N. They have unexpectedly turned up at Farmer John's farm, so the unfailingly polite Farmer John is attempting to give them gifts.
To this end, Farmer John has brought out his infinite supply of gifts, and Nhoj's cows have queued up in front of him, with cow 1 at the head of the queue and cow N at the tail. Farmer John was expecting that at every timestep, the cow at the head of the queue would take a gift from Farmer John and go to the tail of the queue. However, he has just realized that Nhoj's cows are not that polite! After receiving her gift, each cow may not go to the tail of the queue, but rather may cut some number of cows at the tail, and insert herself in front of them. Specifically, cow i will always cut exactly C_i cows ( 0 ≤ c_i ≤ N-1 ).
Farmer John knows that some cows might receive multiple gifts; as he has an infinite supply, this does not worry him. But he is worried that some cows might become unhappy if they do not get any gifts.
Help Farmer John find the number of cows who never receive any gifts, no matter how many gifts are handed out.

SAMPLE INPUT:

3
1 2 0

SAMPLE OUTPUT:

1

翰林USACO课程体系流程图

以上就是关于【USACO 2017 December Contest, Platinum Problem 3. Greedy Gift Takers】的解答，如需了解学校/赛事/课程动态，可至翰林教育官网获取更多信息。

往期文章阅读推荐：

2026 NOAI国际AI奥赛中国站即将开考！赛事地址&日程已出！

2027 USAAIO美国AI奥赛启动报名！MIT/谷歌/Jane Street集体站台！