1342: [Baltic2007]Sound静音问题
Description
静音问题 数字录音中，声音是用表示空气压力的数字序列描述的，序列中的每个值称为一个采样，每个采样之间间隔一定的时间。 很多声音处理任务都需要将录到的声音分成由静音隔开的几段非静音段。为了避免分成过多或者过少的非静音段，静音通常是这样定义的：m个采样的序列，该序列中采样的最大值和最小值之差不超过一个特定的阈值c。 请你写一个程序，检测n个采样中的静音。
Input
第一行有三个整数n，m，c（ 1<= n<=1000000，1<=m<=10000， 0<=c<=10000），分别表示总的采样数、静音的长度和静音中允许的最大噪音程度。第2行n个整数ai (0 <= ai <= 1,000,000)，表示声音的每个采样值，每两个整数之间用空格隔开。
Output
列出了所有静音的起始位置i（i满足max(a[i, . . . , i+m−1]) − min(a[i, . . . , i+m−1]) <= c），每行表示一段静音的起始位置，按照出现的先后顺序输出。如果没有静音则输出NONE。
Sample Input
7 2 0
0 1 1 2 3 2 2
0 1 1 2 3 2 2
Sample Output
2
6
6
单调队列裸裸的。。。
#include<cstdio>
#define MaxN 1000010
int N,M,c,cnt;
int A[MaxN];
int st1[MaxN],w1,t1;
int st2[MaxN],w2,t2;
int Get(){
char Ch;
int Sign=1;
while ((Ch=getchar())<'0'||Ch>'9')
if (Ch=='-') Sign=-1;
int Num=Ch-'0';
while ((Ch=getchar())>='0'&&Ch<='9')
Num=Num*10+Ch-'0';
return Num*Sign;
}
int main(){
N=Get(); M=Get(); c=Get();
w1=w2=1;
for (int i=1;i<=N;++i){
A[i]=Get();
while ( w1<=t1 && A[i]<A[st1[t1]] ) --t1;
st1[++t1]=i;
while ( st1[w1] <= i-M ) ++w1;
while ( w2<=t2 && A[i]>A[st2[t2]] ) --t2;
st2[++t2]=i;
while ( st2[w2] <= i-M ) ++w2;
if (i>=M){
int s=A[st2[w2]]-A[st1[w1]];
if (s<=c){
++cnt;
printf("%d\n",i-M+1);
}
}
}
if (!cnt) printf("NONE\n");
}
评论 (0)
