/ CWOI / 题库 /

2017.07.10 P4 博客点击率

2017.07.10 P4 博客点击率

题目描述

有一个博客,初始赞数为0,每个人都会浏览这篇博客,如果这个人期望的赞数大于博客的赞数,他就会赞这篇博客,如果小于这篇博客,就踩一下(博客赞数-1),相同就不操作。询问对于每个k,对于前1~k 的人按照一个顺序浏览,求一种顺序使得博客最后的赞数最大,输出这个最大的赞数。

输入格式

第一行一个整数n,表示人数
第二行n 个整数,第i 个数表示第i 个人的期望赞数ai

输出格式

输出前k 个人最大的赞数,k 从1~n 变化

样例1

输入

4
2 0 2 2

输出

1
1
2
2

样例2

输入

7
2 -3 -2 5 0 -3 1

输出

1
0
-1
0
1
1
2

数据范围

对于 30%的数据,1 <= n <= 100,-100 <= ai <= 100
对于 100%的数据,1 <= n <= 5 * 10 ^ 5,-5 * 10 ^ 5 <= ai <= 5 * 10 ^ 5

限制

4s

来源

Codeforce773E
CWOI新高二专题测试八

信息

难度
7
分类
动态规划 | 数据结构 | 线段树 点击显示
标签
(无)
递交数
6
已通过
1
通过率
17%
上传者