UVA12174 Shuffle的播放记录如何为？
摘要：题目传送门 从题目中我们可以看出，这道题显然是用滑动窗口来完成的。 是的，滑动窗口！而且这个滑动窗口比较容易维护，因为它窗口的大小"基本"固定，（因为还需要考虑不完整的段），只需使用一个变
题目传送门
从题目中我们可以看出，这道题显然是用滑动窗口来完成的。
是的，滑动窗口！而且这个滑动窗口比较容易维护，因为它窗口的大小"基本"固定，（因为还需要考虑不完整的段），只需使用一个变量来标记，而且所有的数都是从1~s的整数，因此，只需用一个数组便可以保存每个数在窗口中出现的次数。在用一个b数组来记录不合法（窗口中含有相同的歌），在最后再用s减去不合法的个数就行了。 代码如下：
#include <bits/stdc++.h>
using namespace std;
int a[1000100],tmp[1000100],b[1000100];
int main(){
int n,m,s;
cin>>m;
while(m--){
cin>>s>>n;
memset(a,0,sizeof(a));
memset(tmp,0,sizeof(tmp));
memset(b,0,sizeof(b));
int ans = s;
int p = 0;//右端
for (int i=1;i<=n;i++){
cin>>a[i];
}
for (int i=1;i<=n+s;i++){
if (i>s){
tmp[a[i-s]]--;
if (tmp[a[i-s]] == 1) p--;
}
tmp[a[i]]++;//个数加一
if (tmp[a[i]]>1&&a[i]) p++;
if (p>0) b[i%s] = 1;//防止溢出
}
int wrongful = 0;
for (int i=0;i<s;i++){
wrongful+=b[i];
}
cout<<ans-wrongful<<endl;
}
return 0;
}
注意： 你的tmp数组必须开得足够大，否则会RE
惨痛教训：