徐老师的摆烂计划
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
徐老师最近接了一个文案的工作
徐老师已经写好了 $n$ 句精彩的句子，他认为第 $i$ 句句子的精彩程度是 $a_i$
我们可以认为一篇文章的精彩程度取决于这篇文章中使用句子的精彩程度
显然，如果这篇文章中的句子精彩程度参差不齐，会显得文章非常不专业
所以徐老师希望尽可能用精彩程度一样的句子组成一篇文章
在一篇文章中，只要不同精彩程度的句子数量不超过 $k$ ，则这篇文章被徐老师认为是可以交差的
例如一篇文章中有五个句子，精彩程度分别 $1,1,2,3,1,2$，那么这篇文章中有 $3$ 种不同精彩程度的句子
但是徐老师实在是太懒了，他不想移动他现在已经写好的句子顺序
所以他只会把连续的句子直接组成一篇文章上交，而现在徐老师希望尽可能少交几篇文章，这样当甲方不满意的时候，他需要修改的文章也少一些
现在徐老师想知道，当 $k = 1 \sim n$ 时，他最少需要交多少篇文章
输入格式
第一行，一个正整数 $n$，表示句子的数量；第二行包含 $n$ 个整数 $a_i$，分别表示每一个句子的精彩程度
对于前 $10\%$ 的数据，$a_i\leq 2$；
对于前 $20\%$ 的数据，$a_i\leq 10$；
对于前 $40\%$ 的数据，$n\leq 1000$；
对于前 $80\%$ 的数据，$n\leq 5\times 10^4$；
对于 $100\%$ 的数据，$1\leq n\leq 10^5,1\leq a_i\leq n$。
输出格式
输出一行包含 $n$ 个整数，表示 $k = 1,2,3, \dots, n$ 时的答案
样例
6
1 1 2 3 1 25 3 1 1 1 1提示
对于 $k = 1$ 时，文章组成方案为 $[1,1],[2],[3],[1],[2]$
对于 $k = 2$ 时，文章组成方案为 $[1,1,2],[3,1],[2]$
对于 $k >=3$ 时，可以用所有句子组成一篇文章
2023暑CSP-S复赛集训模拟赛四
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 3
- 开始于
- 2023-7-31 22:15
- 结束于
- 2023-8-10 22:15
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 20
