[传智杯 #2 决赛] 课程安排
题目描述
传智播客的课表上按顺序提供 $n$ 节课程,课程可能是 Java、Python 或者前端开发等等,我们用不超过 $n$ 的正数代表每一节课程的种类。学员可以从这个课程序列选取连续的一小段的课程序列,作为一周的学习任务。
为了使学习任务不那么枯燥,学员不想连续上两节相同的课。特殊的,这一周学习任务的开头和结尾也不能是相同的课。为了保证学习效果,一周内至少要学完 $l$ 节课程。
请问,我们有多少种合法的选课方案?
两种选课方案,只要选取的课程序列在原序列的开头和结尾有至少一个位置不一致,那么就可以认为是不同的选课方案。注意,即使 $l$ 是 1,一周只安排一次课也是不合法的,至少需要安排 2 次课。
输入格式
每个测试点由多组数据组成。
第一行为一个整数 $T$,代表数据的组数。
对于每组数据,第一行输入两个正整数 $n$ 和 $l$。接下来一行输入 $n$ 个非负整数 $c_i$ 表示课程种类编号。
输出格式
对于每组数据,输出一行一个数,表示方案数。
样例 #1
样例输入 #1
2
3 1
1 2 3
5 3
1 2 3 1 1
样例输出 #1
3
2
提示
样例解释
对于第一组数据,有 [1,2] 和 [2,3] 和 [1,2,3] 三种方法。
对于第二组数据,由于至少要选 3 门课,只有 [1,2,3] 和 [2,3,1] 两种方法。
数据范围
测试数据不超过 5 组,$1\le N \le 5 \times 10^5$,$1\le l,c_i \le N$
题目分析
双指针
题目要求找出序列中所有极大的相邻两数不同的区间
求出序列内左端点和右端点不同,且区间长度大于等于 $l$ 的区间个数
所以考虑像 滑动窗口 那样直接用双指针扫一遍
假设扫到某个点,则符合要求的数量为以这个点为右端点的区间长度大于等于$l$的区间个数减去左端点和右端点相同且区间长度大于等于 $l$ 的个数
左端点和右端点相同且区间长度大于等于 $l$ 的个数用桶计数的方法扫一遍整个区间即可
每次扫完桶得清零
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 500010;
int T;
int n, L;
int c[N], cnt[N];
void solve()
{
cin >> n >> L;
long long s = 0;
for (int i = 1; i <= n; i++)
cin >> c[i];
for (int l = 1, r = 1; l <= n; l = r = r + 1)
{
while (r < n && c[r] != c[r + 1])
r++;
for (int i = l; i <= r; i++)
if (i - l + 1 >= L)
cnt[c[i - L + 1]]++, s += i - l + 2 - L - cnt[c[i]];
for (int i = l; i <= r; i++)
cnt[c[i]] = 0;
}
cout << s << '\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> T;
while (T--)
{
solve();
}
return 0;
}
符合要求的数量为以这个点为右端点的区间长度大于等于l的区间个数减去左端点和右端点相同且区间长度大于等于 l 的个数
这里是为什么这样呢
符合要求的数量为以这个点为右端点的区间长度大于等于l的区间个数减去左端点和右端点相同且区间长度大于等于 l 的个数
这里是为什么这样呢