课程安排 | Serendipity

type

status

date

slug

summary

题目描述

传智播客的课表上按顺序提供节课程，课程可能是 Java、Python 或者前端开发等等，我们用不超过的正数代表每一节课程的种类。学员可以从这个课程序列选取连续的一小段的课程序列，作为一周的学习任务。

为了使学习任务不那么枯燥，学员不想连续上两节相同的课。特殊的，这一周学习任务的开头和结尾也不能是相同的课。为了保证学习效果，一周内至少要学完节课程。

请问，我们有多少种合法的选课方案？

两种选课方案，只要选取的课程序列在原序列的开头和结尾有至少一个位置不一致，那么就可以认为是不同的选课方案。注意，即使是 1，一周只安排一次课也是不合法的，至少需要安排 2 次课。

输入格式

每个测试点由多组数据组成。

第一行为一个整数，代表数据的组数。

对于每组数据，第一行输入两个正整数和。接下来一行输入个非负整数表示课程种类编号。

输出格式

对于每组数据，输出一行一个数，表示方案数。

样例 #1

样例输入 #1

样例输出 #1

提示

样例解释

对于第一组数据，有 [1,2] 和 [2,3] 和 [1,2,3] 三种方法。

对于第二组数据，由于至少要选 3 门课，只有 [1,2,3] 和 [2,3,1] 两种方法。

数据范围

测试数据不超过 5 组，，

题解

以下 l 均为左指针，k为题目中说的 l ，及课程长度。

本人错误写法1：

枚举左端点 l ，双指针找出最后一个 r ，满足 [ l , r ] 中没有两个连续的相同课的位置且不等与。显然这样是错的。例如 [ 1 , 2 , 3 , 1 , 2 ] 会在 r=4 结束而不会往后。

本人错误写法2：

枚举左端点 l ，双指针找出最后一个 r ，满足 [ l , r ] 中没有两个连续的相同课的位置，在这期间统计与相等且被课程数量满足题目要求数量的个数，在最后统计时减去。这样做如果 r 不重新回到 l 开始统计会导致后面在计数是漏掉一部分情况，例如 [ 1 , 2 , 3 , 2 , 1 , 1 ] 时无法正确计算前指针为 2 的个数，会漏掉。但是如果将 r 重新回到 l 开始计数会导致超时的问题。

正解：

枚举左端点 l ，双指针找出最后一个 r ，满足 [ l , r ] 中没有两个连续的相同课的位置。额外开一个数组 a ，记录下长度满足条件后的所有的课程数目。

例如上面的图片，我们扫完第一遍后得出 a 的数组如下，当 l 向后移动一位时 l + k -1 不在我们需要特殊判断的头尾是否相等的范围内，所以在做完时只需将 a [ l + k - 1 ] - 1 即可。

完整代码：