UVA 12174 播放器,滑动窗口

Posted by Cww97 on 2016-02-18

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/50683437
题目

一开始写ok数组的时候for前面一段,后面一段
都特殊处理,然后先是RTE,找了半天发现数组下标出现负的了
改了之后WA,

最后看了眼刘的代码
刘的处理方式是在前面加s个空的格子
然后穷举1到s能否做起点

贴代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=2001000;
int i,j,n,s,vis[N],a[N],ans,cnt;
bool ok[N];

bool check(int x){
for (j=x;j<=n+s;j+=s)
if (!ok[j])return 0;
return 1;
}

int main(){
//freopen("fuck.in","r",stdin);
int T;scanf("%d",&T);
for (;T--;){
scanf("%d%d",&s,&n);
memset(a,-1,sizeof(a));
memset(ok,0,sizeof(ok));
memset(vis,0,sizeof(vis));
for (i=1;i<=n;i++)scanf("%d",&a[s+i]);
cnt=0;
for (i=1;i<=n+s;i++){ //i为起点
if (cnt==s) ok[i]=1;
if (i<=s&&cnt==i-1)ok[i]=1;//left
if (i>n+1&&cnt==n+s-i+1)ok[i]=1;//right
if (a[i]!=-1&&--vis[a[i]]==0)cnt--;
if (a[s+i]!=-1&&vis[a[s+i]]++==0)cnt++;
}
ans=0; //begin
for (i=1;i<=s;i++) if(check(i))ans++;
if (ans==n+1)ans=s;
printf("%d\n",ans);
}
return 0;
}
这里写图片描述
这里写图片描述