USYS 学生宿舍洗澡时间优化：卷王属性与最短时间算法

USYS 学生宿舍洗澡时间优化：卷王属性与最短时间算法

在 USYS 学生宿舍，N 个人住在一起，每个人都用一个大写字母表示不同的卷王类型。每个人洗澡时间为 1 个单位时间，但相同类型的卷王需要间隔 T 个单位的冷却时间才能洗澡，否则会触发隐藏属性，浴室将被摧毁。由于热水供应有限，需要找到一种最优的洗澡顺序，使 N 个人总洗澡时间最短。

输入

第一行，两个整数，分别表示 T 和 N。 第二行，N 个整数，表示 N 个人的类型，用大写字母表示。

输入数据说明：

1≤N≤10000 0≤T≤100

输出

N 个人最短洗澡总时间

样例输入

2 6
A A A B B B

样例输出

8

样例说明

洗澡的顺序为

A -> B -> (冷却) -> A -> B -> (冷却) -> A -> B

算法 1：贪心 + 优先队列

1. 统计每个类型的人需要洗澡的次数。
2. 从次数最多的人开始，每次选择一个可以洗澡的人加入队列。
3. 更新队列中所有人的冷却时间。
4. 优先选择冷却时间最短的人加入队列。
5. 重复步骤 2-4，直到所有人的洗澡次数为 0。

时间复杂度： O(NlogN)

参考文献：

C++ 代码：

// 代码实现

算法 2：动态规划

时间复杂度：

参考文献：

C++ 代码：

// 代码实现