1005E1 Median on Segments (Permutations Edition) 【思维+无序数组求中位数】

百度之星初赛原题：戳这里

题意：n个不同的数，求中位数为m的区间有多少个。

解题思路：

此题的中位数就是个数为奇数的数组中，小于m的数和大于m的数一样多，个数为偶数的数组中，小于m的数比大于m的数少一。因此，维护比m小和比m大的数就行。

m~n进行处理，比m大的cnt++，比m小的cnt--，用vis数组记录每个cnt值的个数。

m~1再进行处理，比m大的cnt++，比m小的cnt--，ans+=vis[cnt]+vis[cnt+1]，vis[cnt]可以理解为是右边有cnt个比m大的数的情况（n为奇数，vis[cnt+1]是右边有cnt个比m大的数的情况（n为偶数。（当然真正的数值并不代表这个意思，因为出现比m小的数时cnt--了，在这里形容是为了便于理解。

这样操作的意思是，先预处理[pos[m],r]的所有情况，在遍历[l,pos[m]]的所有情况时，直接求出答案。

代码比文字好理解：

 1 #include <bits/stdc++.h>

 2 typedef long long ll;

 3 const int maxn = 1e6+10;

 4 const int inf = 0x3f3f3f3f;

 5 const ll mod = 998244353;

 6 using namespace std;

 7 int a[maxn];

 8 map<int,int>vis;

 9 int main(){

10     int n, m;

11     scanf("%d %d", &n, &m);

12     int pos = 0;

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

14         scanf("%d",a+i);

15         if(a[i] == m) pos = i;

16     }

17     int cnt = 0;

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

19         if(a[i] > m) ++cnt;

20         if(a[i] < m) --cnt;

21         vis[cnt]++;

22     }

23     cnt = 0;

24     ll ans = 0;

25     for(int i = pos; i >= 1; --i) {

26         if(a[i] > m) --cnt;

27         if(a[i] < m) ++cnt;

28         ans += vis[cnt]+vis[cnt+1];//此时m左边的大小情况为cnt，要找右边为cnt和cnt+1的情况

29     }

30     printf("%lld\n", ans);

31     return 0;

32 }

巴特西

1005E1 Median on Segments (Permutations Edition) 【思维+无序数组求中位数】

最新文章

热门文章