https://ac.nowcoder.com/acm/problem/19913
题目描述
给出1-n的一个排列,统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后,位于中间的数。
输入描述:
第一行为两个正整数n和b ,第二行为1~n 的排列。
输出描述:
输出一个整数,即中位数为b的连续子序列个数。
示例1
输入
7 4 5 7 2 4 3 1 6
输出
4
根据排列的特点,序列中只有一个b,我们可以以b为标准0,把其他数字表示成-1,1;
以题目样例为例:
5 7 2 4 3 1 6
即:1 1 -1 0 -1 -1 1
表示成这样以后,长度为奇数的连续子序列,就是区间和为0的连续子序列。区间和的求法,一种方法是前缀和。
之后以b为中心向右求前缀和,向左求后缀和。
在这里,笔者是分为了三种情况讨论:
【1】连续子序列全部位于b位置的左边,遍历查看0的个数;
【2】连续子序列全部位于b位置的右边,遍历查看0的个数;
【3】连续子序列跨越了b,位于b的左右两边,所以我写了个暴力的两重循环。
#include <bits/stdc++.h> #include <cstdio> //#define local using namespace std; typedef unsigned long long ull; typedef long long ll; const int N = 1e5+5; const int inf = 0x3f3f3f3f; int n,b,a[N],pos; int main() { #ifdef local freopen("input.txt","r",stdin); #endif // local scanf("%d%d",&n,&b); for(int i=1; i<=n; i++) { scanf("%d",&a[i]); if(a[i]==b) a[i]=0,pos=i; else if(a[i]>b) a[i]=1; else a[i]=-1; } for(int i=pos;i>1;i--) a[i-1]+=a[i]; for(int i=pos;i<n;i++) a[i+1]+=a[i]; // for(int i=1;i<=n;i++) // printf("%d ",a[i]); int ans=0; for(int i=0; i<pos; i+=2)//左边,i+=2,保证长度为奇数,从0开始是因为b一个数时也合法 if(a[pos-i]==0) ans++; for(int i=2; i<=n-pos; i+=2)//右边, if(a[pos+i]==0) ans++; for(int i=pos+1;i<=n;i++)//左右两边 { for(int j=1;j<pos;j++) { if(a[i]+a[j]==0) ans++; } } printf("%d\n",ans); return 0; }