P1627 中位数

题目描述

给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。

输入输出格式

输入格式：

第一行为两个正整数n和b，第二行为1~n的排列。

【数据规模】

对于30%的数据中，满足n≤100；

对于60%的数据中，满足n≤1000；

对于100%的数据中，满足n≤100000,1≤b≤n。

输出格式：

输出一个整数，即中位数为b的连续子序列个数。

输入输出样例

输入样例#1：

7 4

5 7 2 4 3 1 6 

输出样例#1：

4

分析

　　首先大于b的设为1，小于b的设为-1，p点为b值的坐标。处理L数组和R数组，L[i]表示p左边有多少个点到p的和为i，R[i]表示p右边有多少个点到p的和为i，那么ans=Σ L[i]*R[0-i]。为了没有负数坐标，所以代码中统一加n。

code

 #include<cstdio>

 int a[];

 int l[],r[],sum[];

 int read()

 {

     int x = , f = ; char ch = getchar();

     for (; ch<''||ch>''; ch = getchar())

         if (ch=='-') f = -;

     for (; ch>=''&&ch<=''; ch = getchar())

         x = x*+ch-'';

     return x*f;

 }

 int main()

 {

     int n = read(), d = read(), p,ans = ;

     for (int x,i=; i<=n; ++i) {

         x = read();

         if (d==x) p = i,a[i] = ;

         else if (x<d) a[i] = -;

         else a[i] = ;

     }

     l[n] = r[n] = ;

     for (int i=p-; i>=; --i) {

         sum[i] = sum[i+]+a[i];

         l[sum[i]+n]++;

     }

     for (int i=p+; i<=n; ++i) {

         sum[i] = sum[i-]+a[i];

         r[sum[i]+n]++;

     }

     for (int i=; i<=*n-; ++i) ans += l[i]*r[*n-i];

     printf("%d",ans);

     return ;

 }

乱搞70

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int a[];

 int read()

 {

     int x = , f = ; char ch = getchar();

     for (; ch<''||ch>''; ch = getchar())

         if (ch=='-') f = -;

     for (; ch>=''&&ch<=''; ch = getchar())

         x = x*+ch-'';

     return x*f;

 }

 int main()

 {

     int n = read(), d = read(), p = -, xcnt = , dcnt = ,ans = ;

     for (int i=; i<=n; ++i) {

         a[i] = read();

         if (d==a[i]) p = i;

         if (p==-) {

             if (a[i]<d) xcnt++;

             else dcnt++;

         }

     }

     int L = p,da = ,xo = ;

     for (int i=; ; i+=) {

         if (a[--L]>d) da++;else xo++;

         if (a[--L]>d) da++;else xo++;

         if (da==xo)    ans++;

         if (L==||L==) break;

     }

     for (int i=; i<=p; ++i) {

         if (i!=) {

             if (a[i-]>d) dcnt--;

             else xcnt--;

         }

         da = dcnt,xo = xcnt;

         for (int j=p+; j<=n; ++j) {

             if (a[j]>d) da++;else xo++;

             if (da==xo) ans++;

         }

     }

     printf("%d",ans);

     return ;

 }