打卡信奥刷题（3016）用C++实现信奥题 P6334 [COCI 2007/2008 #1] SREDNJI

P6334 [COCI 2007/2008 #1] SREDNJI

题目描述

给定一个长度为n nn的1 ∼ n 1\sim n1∼n的排列a 1 , … , a n a_1,\dots ,a_na1​,…,an​，请你找出这个排列有多少个长度为奇数的子串的中位数为B BB。

• 子串定义：把这个排列从开头（可能无）和从结尾（可能无）分别删去一些数后得到的剩下的数列。

• 中位数定义：将一个数列从小到大排序后排在中间的那个数字。

输入格式

输入第一行为两个整数n , B n,Bn,B。

第二行包含n nn个整数，为一个1 ∼ n 1\sim n1∼n的排列。

输出格式

输出中位数为B BB的长度为奇数的子串的个数。

输入输出样例 #1

输入 #1

5 4 1 2 3 4 5

输出 #1

2

输入输出样例 #2

输入 #2

6 3 1 2 4 5 6 3

输出 #2

1

输入输出样例 #3

输入 #3

7 4 5 7 2 4 3 1 6

输出 #3

4

说明/提示

样例3 33解释

所有可能的情况：47 2 45 7 2 4 35 7 2 4 3 1 6。

数据规模与约定

对于100 % 100\%100%的数据，保证1 ≤ n ≤ 10 5 1\le n\le 10^51≤n≤105，1 ≤ B ≤ n 1\le B\le n1≤B≤n。

说明

题目译自 COCI2007-2008 CONTEST #1T5 SREDNJI

C++实现

#include<bits/stdc++.h>usingnamespacestd;intn,b;inta[100005];intsum1,sum2;intcnt[200005];//注意考虑负数情况，故数组开两倍intpos;intmain(){scanf("%d%d",&n,&b);for(inti=1;i<=n;i++)scanf("%d",&a[i]);for(inti=1;i<=n;i++)if(a[i]==b){pos=i;break;}for(inti=0;i<=pos-1;i++)//由于i的范围为1~pos,这里直接枚举i-1的范围为0~pos-1{if(a[i]>b)sum1++;if(a[i]<b)sum2++;cnt[sum1-sum2+n]++;//用桶计数，+n排除负数情况}intans=0;for(inti=pos;i<=n;i++){if(a[i]>b)sum1++;if(a[i]<b)sum2++;ans+=cnt[sum1-sum2+n];//统计答案}printf("%d\n",ans);return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容