hdu4908（中位数）-白红宇

hdu4908（中位数）

阅读量：6832 次

发布时间：2019-06-26

本文共 1559 字，大约阅读时间需要 5 分钟。

传送门：

题意：给一个序列，里面是1～N的排列，给出m，问以m为中位数的奇数长度的序列个数。

分析：先找出m的位置，再记录左边比m大的状态，记录右边比m大的状态，使得左右两边状态平衡（和为0）就是满足的序列。

举例：

7 4

1 5 4 2 6 3 7

ans=8

m的位置pos=3：0

左边：0 1

右边：-1 0 -1 0

那么左边的0可以和右边的两个0组合（<1 5 4 2 4>,<1 5 4 2 6 3 7>）.

左边的1和右边的两个-1组合（<5 4 2>,<5 4 2 6 3>）.

中间pos可以和左右两边为0的组合还有自己本身（<1 5 4>,<4 2 6>,<4 2 6 3 7>,<4>）

因此总共8个。

5 3

1 2 3 4 5

ans=3

3的位置pos=3:0

左边：-2 -1

右边：1 2

左边-1可以和右边1可以组合（<2 3 4>）

左边-2和可以右边-2组合（<1 2 3 4 5>）.

加上自己本身，因此ans=3.

#pragma comment(linker,"/STACK:1024000000,1024000000")#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #define LL long long#define mod 100000000#define inf 0x3f3f3f3f#define eps 1e-6#define N 60010#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define PII pair
                   
                    using namespace std;inline int read(){ char ch=getchar();int x=0,f=1; while(ch>'9'||ch<'0'){ if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x*f;}int n,m,pos;int a[N<<1],c[N<<1];int main(){ while(scanf("%d%d",&n,&m)>0) { for(int i=1;i<=n;i++) { scanf("%d",&a[i]); if(a[i]==m)pos=i; } int res=0,ans=1; memset(c,0,sizeof(c)); for(int i=pos-1;i>=1;i--) { if(a[i]>m)res++; else res--; if(res==0)ans++; c[res+n]++;//记录某种状态数量 } res=0; for(int i=pos+1;i<=n;i++) { if(a[i]>m)res++; else res--; if(res==0)ans++; ans+=c[n-res];//加上左边记录下来的相反状态之和 } printf("%d\n",ans); }}