网站建设与管理领导小组,洛阳网络运营公司,如何快速做h5网站,手游传奇网站999服涉及知识点#xff1a;已知中位数的题的一般思路
题目描述
给出1~n的一个排列#xff0c;统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后#xff0c;位于中间的数。
输入描述:
第一行为两个正整数n和b #xff0c;第二行…涉及知识点已知中位数的题的一般思路
题目描述
给出1~n的一个排列统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后位于中间的数。
输入描述:
第一行为两个正整数n和b 第二行为1~n 的排列。
输出描述:
输出一个整数即中位数为b的连续子序列个数。
示例1
输入
复制7 4 5 7 2 4 3 1 6
7 4
5 7 2 4 3 1 6
输出
复制4
4
备注:
对于30%的数据中满足 n≤100n \le 100n≤100对于60%的数据中满足 n≤1000n \le 1000n≤1000对于100%的数据中满足 n≤100000,1≤b≤nn \le 100000,1 \le b \le nn≤100000,1≤b≤n。
想法
没有想法不会微笑。好吧实现不出来。就是标记一下目标元素的下标然后分两种情况一是子序列以目标元素之前的元素开头到目标元素然后向后延展二是子序列以目标元素开头向后延展。这里实现不出来想不到。
2.3
答疑
这题不会写正常我看他用的方法还是我想不到的。我们关心的不是具体的值而是这个数字比目标值中位数大还是比目标值小。所以我们把比目标值大的置为1比目标值小的置为-1目标值置为0。然后以0目标值为中心分别向两边延申算子串和即子串中各个抵消后大于0或小于0的个数。最后把0的两端值相加为0互为相反数的配对看有多少对可以配对。以后遇到中位数的题都可以先往这个方向想。
代码
#includebits/stdc.h using namespace std; int n,b; int a[100010]; int r[300010],l[300010]; int main(){ int sign; scanf(%d%d,n,b); for(int i1;in;i){ scanf(%d,a[i]); if(a[i]b) a[i]1; else if(a[i]b) a[i]-1; else if(a[i]b) { a[i]0; signi;//记录中位数的下标 } } for(int isign-1;i0;i--){//后缀和目标值左端 a[i]a[i]a[i1]; l[a[i]100000];//下标平移因为下标可能是负数 } for(int isign1;in;i){//前缀和目标值右端 a[i]a[i]a[i-1]; r[a[i]100000]; } int ans0; for(int i0;i200000;i){ ansl[i]*r[200000-i];//左右匹配 } ansl[100000]r[100000]1;//左右两端为0的值还可以直接到中位数构成子串加一是因为直接一个中位数也满足条件 coutans; }
