统计频次：用数组统计 $26$ 个字母的出现次数，记最高频次为 $f_{max}$ ，与其相等的任务个数为 $k$ 。
关键结论：最短时间

$ans=\max(|tasks|,(f_{max}-1)*(n+1)+k)$
- 解释：将最高频任务分成 $f_{max}$ 组，其中前 $f_{max}-1$ 组需要被 $n$ 的冷却间隔撑开，每组长度为 $(n+1)$ （包含 $1$ 个最高频任务和 $n$ 个空位/其他任务）；最后再放入与 $f_{max}$ 持平的 $k$ 个任务收尾。若其他任务足以填满空位，则答案至少是 $|tasks|$ 。
复杂度：计数与扫描均为常数级字母表规模，整体 $O(|tasks|)$ ，空间 $O(26)$ 。

P3409.第1题-最优任务调度

1000ms

Difficulty: 3

所属公司 : 大疆

算法与标签>贪心算法

题目内容

给你一个用字符串 $tasks$ 表示的 $CPU$ 需要执行的任务列表，用字母 $A$ 到 $Z$ 表示，以及一个冷却周期 $n$ 。每个周期允许完成一项任务。任务可以按任何顺序完成，但有一个限制:两个相同种类的任务之间必须有长度为 $n$ 的冷却周期。返回完成所有任务所需要的最短周期数。

例 $1$ :对于 $n=2$ ，任务列表 $AAABBB$ ，其一种最优执行顺序为

$A->B->idle->A->B->idle->A->B$

上述执行序列满足任意 $A$ 或 $B$ 任务间都有 $2$ 个周期的冷却，最短周期数为 $8$

例 $2$ :对于 $n=3$ ，任务列表 $AAABBB$ ，其一种最优执行顺序为

$A->B->idle->idle->A->B->idle->idle->A->B$

上述执行序列满足任意 $A$ 或 $B$ 任务间都有 $3$ 个周期的冷却，最短周期数为 $10$

例 $3$ :对于 $n=1$ ，任务列表 $ACABDB$ ，其一种最优执行顺序为

$A->B->C->D->A->B$

上述执行序列满足任意同种任务间都有 $1$ 个周期的冷却,最短周期数为 $6$

冷却周期 $n$ : $2<=n<10$

$task$ 字符串长度:长度 $<400$

$task$ 字符串:仅包含大写字母

成所有任务所需的最短周期数

输入

2
6
AAABBB

输出

输入

预期输出（选填）