首页 > 代码库 > BestCoder Sequence

BestCoder Sequence

2024-07-15 15:22:32   223人阅读

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 }
View Code

 


联系
我们