首页 > 代码库 > BestCoder Sequence
BestCoder Sequence
hdu4908:http://acm.hdu.edu.cn/showproblem.php?pid=4908
题意::给定一个序列,1-n的数字,选定一个作为中位数m,要求有多少连续子序列满足中位数是m
题解;自己不会做,然后别人给了一个O(n)的算法,瞬间吓cry。这个算法不好解释,还是看看代码,然后自己画个图就出来了。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 long long last; 7 long long ans[100003]; 8 long long a[40005]; 9 int m,n,cnt,ct,pos;10 int main(){11 while(~scanf("%d%d",&n,&m)){12 memset(ans,0,sizeof(ans));13 memset(a,0,sizeof(a));14 last=0;cnt=ct=50000;15 for(int i=1;i<=n;i++){16 scanf("%I64d",&a[i]);17 if(a[i]==m)18 pos=i;19 }20 ans[cnt]++;21 for(int i=pos+1;i<=n;i++){22 if(a[i]<m)ans[--cnt]++;23 else ans[++cnt]++;24 }25 last+=ans[ct];26 for(int i=pos-1;i>=1;i--){27 if(a[i]<m){28 last+=ans[++ct];29 }30 else{31 last+=ans[--ct];32 }33 }34 printf("%I64d\n",last);35 }36 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。