BZOJ 1303: [CQOI2009]中位数图

本文主要是介绍BZOJ 1303: [CQOI2009]中位数图，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1303: [CQOI2009]中位数图

Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 3297 Solved: 2033
[ Submit][ Status][ Discuss]

Description

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

Input

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

Output

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

Sample Input

7 4
5 7 2 4 3 1 6

Sample Output

HINT

第三个样例解释：{4}, {7,2,4}, {5,7,2,4,3}和{5,7,2,4,3,1,6}
N<=100000

Source

【思路】

前缀和问题，连续子序列，中位数，瞬间降低了难度，大于赋值为1 小于赋值为-1 等于赋值为 0

又Sum[r]=Sum[l-1] ans++;

处理有可能会有小于0 的情况故加个n

【代码】

/*
* Date: 4/1/2018
* Tile: 1303
* AU: SIZ
* Cate: 思维，前缀和
* WA:3
*/#include <iostream>
#include <bits/stdc++.h>
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=1e5+5;
using namespace std;
int a[MAXN];
int sum[MAXN];
map<int,int>mp;
int main()
{mp.clear();int n;int b;memset(sum,0,sizeof(sum));cin>>n>>b;for(int i=1;i<=n;i++){cin>>a[i];}int p=-1;for(int i=1;i<=n;i++){if(a[i]==b)a[i]=0,p=i;elsea[i]=(a[i]>b?1:-1);sum[i]=sum[i-1]+a[i];if(p==-1)mp[sum[i]+n]++;}mp[n]++;int ans=0;for(int i=p;i<=n;i++){//    cout<<sum[i]<<" "<<mp[sum[i]+n]<<endl;ans+=mp[sum[i]+n];}cout<<ans<<endl;return 0;
}

123

这篇关于BZOJ 1303: [CQOI2009]中位数图的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！