P13504 [OOI 2024] More Gifts

信息学闭赛的主办方决定为参赛选手准备礼物。共准备了 $k$ 盒完全相同的礼品盒，每盒中有 $n$ 个礼物。这些礼物按顺序叠放在一起，最上面是 $a_1$ 型礼物，下面是 $a_2$ 型，以此类推，最底下是 $a_n$ 型礼物。 礼物的分发方式如下：首先，从第一盒礼物的顶部依次发放，直到第一盒发完；然后从第二盒的顶部依次发放，直到第二盒发完；依此类推，最后发放第 $k$ 盒礼物。 每位参赛者可以一次性领取多个礼物，因此分发时会先给第一个参赛者发礼物，然后是第二个，依次进行。已知如果某位参赛者收到超过 $t$ 种不同类型的礼物，他会太高兴，导致比赛发挥失常。为了让大家都能正常参赛，主办方决定每位参赛者收到的不同类型礼物不能超过 $t$ 种（注意，同一种礼物可以收到多个）。 主办方希望让信息学闭赛更具专属感，于是想邀请尽量少的参赛者。请你帮助主办方计算，最少需要邀请多少参赛者，才能让所有礼物都被分完，并且每位参赛者收到的不同类型礼物不超过 $t$ 种。

第一行输入三个整数 $n$、$k$、$t$（$1 \le n \le 300\,000$，$1 \le k, t \le 10^9$），分别表示每盒礼物的数量、礼品盒的数量，以及每位参赛者最多能收到的不同类型礼物数。 第二行输入 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示每盒礼物从上到下的类型顺序。

输出一个整数，表示最少邀请多少位参赛者，才能满足所有礼物都被分发且每位参赛者收到的不同类型礼物不超过 $t$ 种。

### 说明 在第一个样例中，每盒礼物从上到下的类型如下（不同颜色表示在盒中的位置）： :::align{center}  ::: 共有 $4$ 盒礼物，礼物的发放顺序如下： :::aligned{center}  ::: 由于 $t=1$，每位参赛者只能收到一种类型的礼物： :::aligned{center}  ::: 在第二个样例中，发放顺序及礼物分组如下： :::aligned{center}   ::: 在第三个样例中，发放顺序如下： :::aligned{center}  ::: 此时一种最优的分配方式如下： :::aligned{center}  ::: ### 计分方式 本题共六组测试。只有通过该组及其所有依赖组全部测试，才能获得该组分数。部分组不要求通过样例测试。 | 组别 | 分值 | 额外约束 | $n$ | $k$ | $t$ | 依赖组 | 备注 | |:------:|:------:|:----------------------:|:--:|:--:|:--:|:---------------:|:-------:| | 0 | 0 | -- | -- | -- | -- | -- | 样例。 | | 1 | 14 | $n \le 100$ | $k \le 10$ | -- | 0 | -- | | 2 | 12 | -- | -- | $t = 1$ | -- | -- | | 3 | 16 | $n \le 1000$ | $k \le 1000$ | -- | 0, 1 | -- | | 4 | 21 | $n \le 1500$ | $k \le 10^6$ | -- | 0, 1, 3 | -- | | 5 | 18 | -- | $k \le 10^6$ | -- | 0, 1, 3, 4 | -- | | 6 | 19 | -- | -- | -- | 0 -- 5 | -- | 翻译由 ChatGPT-4.1 完成。