本文主要是介绍CQOI2009中位数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
CQOI2009中位数
给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。
输入格式：
第一行为两个正整数n和b ，第二行为1~n 的排列。
输出格式：
输出一个整数，即中位数为b的连续子序列个数。
样例输入：
5 4 1 2 3 4 5 ----------- 6 3 1 2 4 5 6 3 ----------- 7 4 5 7 2 4 3 1 6
样例输出：
5 ----------- 1 ----------- 4
数据范围：
编号 1 2 3 4 5 6 7 8 9 10
N 10 50 100 300 1000 3600 10000 25000 55555 100000
时间限制：
2000
空间限制：
512000
提示：
第三个样例解释：{4}, {7,2,4}, {5,7,2,4,3}和{5,7,2,4,3,1,6}。
解析：把比中位数小的改为-1，自己为0，比它大的为1，在爆枚后用乘法原理。
#include<bits/stdc++.h> using namespace std; #define N 100001 #define PER(i,a,b) for(int i=a;i<=b;i++) #define REP(i,a,b) for(int i=a;i>=b;i--) int n; int a[N]; int hz1[N],hz2[N]; int hy1[N],hy2[N]; int let[N]; int b,wei,ans; int main() { cin>>n>>b; PER(i,1,n) { cin>>a[i]; if (a[i]<b)let[i]=-1; else if (a[i]==b) { let[i]=0; wei=i; } else let[i]=1; } int cnt=0; REP(i,wei,1) { cnt+=let[i]; if (cnt>=0) hz1[cnt]++; else hz2[ abs (cnt)]++; } cnt=0; PER(i,wei,n) { cnt+=let[i]; if (cnt>=0) hy1[cnt]++; else hy2[ abs (cnt)]++; } ans+=hy1[0]*hz1[0]; PER(i,1,n) { ans+=hy1[i]*hz2[i]; ans+=hy2[i]*hz1[i]; } cout<<ans; } 这篇关于CQOI2009中位数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
