FZU 2019 排列

本文主要是介绍FZU 2019 排列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

思路：枚举起点终点是O(n^2)是会超时的，是中位数的话证明：大于他的和小于他的数是相等的，那么扫描一遍b左边，大于的的话cnt++,否则cnt--,如果cnt==0的话，证明这一边有一个答案，然后再记录cnt值出现的情况，然后扫描一遍b的右边，大于的话cnt--，否则cnt++,对于每个cnt，都有ans+=num[cnt],这样的原因就是中位数的特征

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 100005;int n,b,arr[MAXN];
int pos[MAXN],neg[MAXN];int main(){int t;scanf("%d",&t);while (t--){scanf("%d%d",&n,&b);memset(pos,0,sizeof(pos));memset(neg,0,sizeof(neg));int sign;for (int i = 1; i <= n; i++){scanf("%d",&arr[i]);if (arr[i] == b)sign = i; }int ans=1,cnt=0;for (int i = sign-1 ; i >= 1; i--){if (arr[i] > b) cnt++;else cnt--;if (cnt == 0)ans++;if (cnt > 0)pos[cnt]++;else neg[-cnt]++;}cnt = 0;for (int i = sign+1; i <= n; i++){if (arr[i] < b) cnt++;else cnt--;if (cnt == 0)ans++;ans += (cnt > 0)?pos[cnt]:neg[-cnt];}printf("%d\n",ans);}return 0;
}

这篇关于FZU 2019 排列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---