首页 > 代码库 > BZOJ 1342: [Baltic2007]Sound静音问题 [单调队列]
BZOJ 1342: [Baltic2007]Sound静音问题 [单调队列]
1342: [Baltic2007]Sound静音问题
Time Limit: 5 Sec Memory Limit: 162 MBSubmit: 835 Solved: 372
[Submit][Status][Discuss]
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 <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;const int N=1e6+5;typedef long long ll;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int n,m,c,a[N],flag;int q1[N],h1,t1,q2[N],h2,t2;int main(){ //freopen("in.txt","r",stdin); n=read();m=read();c=read(); h1=h2=1;t1=t2=0; for(int i=1;i<=n;i++){ a[i]=read(); while(h1<=t1&&i-q1[h1]+1>m) h1++; while(h2<=t2&&i-q2[h2]+1>m) h2++; while(h1<=t1&&a[q1[t1]]<=a[i]) t1--; q1[++t1]=i; while(h2<=t2&&a[q2[t2]]>=a[i]) t2--; q2[++t2]=i; if(i-m+1>=1&&a[q1[h1]]-a[q2[h2]]<=c) printf("%d\n",i-m+1),flag=1; } if(!flag) puts("NONE");}
BZOJ 1342: [Baltic2007]Sound静音问题 [单调队列]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。