hdu4908 中位数子串
子串 中位数
2023-09-11 14:14:00 时间
题意:
给你N个数字组成的数列,然后问你这里面有多少个是以M为中位数的子序列。
(1) 就是只有他自己的那种情况 那么sum+1
(2) 从自己开始向左延伸,x, x - 1, x - 2 ...这种可以记录大于m的个数max和小于m的个数min当两个数相等的时候(min == max)就 sum++,然后在这样 mark[max - min]++;记录差值产生的次数,可以开两个数组,一个寸正差,一个存负差,或者直接开一个容器,我开的是容器,这个地方随意
给你N个数字组成的数列,然后问你这里面有多少个是以M为中位数的子序列。
思路:
首先分四中简单的情况求(1) 就是只有他自己的那种情况 那么sum+1
(2) 从自己开始向左延伸,x, x - 1, x - 2 ...这种可以记录大于m的个数max和小于m的个数min当两个数相等的时候(min == max)就 sum++,然后在这样 mark[max - min]++;记录差值产生的次数,可以开两个数组,一个寸正差,一个存负差,或者直接开一个容器,我开的是容器,这个地方随意
(3) 从自己开始向又延伸,跟上面的操作一样,唯独就是在mark[max - min]++那不一样,这一步不用记录差值的出现次数,而是直接算 sum += mark[min-max],这里很简单,就是优化了暴力,这个题目如果直接暴力是O(n^2)的,这样算出来是O(N)的。不是很难理解就不多解释了,还不懂得看看下面的代码就懂了,水题一道。
#include<stdio.h> #include<map> #define N 44000 using namespace std; map<int ,int>mark; int num[N] ,L[N] ,R[N]; int main () { int sum ,n ,m ,i ,mk; while(~scanf("%d %d" ,&n ,&m)) { for(i = 1 ;i <= n ;i ++) { scanf("%d" ,&num[i]); if(num[i] == m) mk = i; } mark.clear(); sum = 0; int min = 0,max = 0; for(i = mk + 1 ;i <= n ;i ++) { num[i] < m ? min++ : max++; if(min == max) sum ++; mark[max - min] ++; } min = 0 ,max = 0; for(i = mk - 1 ;i >= 1 ;i --) { num[i] < m ? min ++ : max ++; if(min == max) sum ++; sum += mark[min - max]; } printf("%d\n" ,sum + 1); } return 0; }
相关文章
- 【BZOJ1396】识别子串&【BZOJ2865】字符串识别(后缀自动机)
- java基础—找出两个字符串中最大的子串
- BZOJ1396 : 识别子串
- LeetCode高频题5:最长回文子串,利用马拉车manacher算加速
- 最长回文子串
- 【看懂LeetCode】3. 无重复字符的最长子串
- 力扣解法汇总1234. 替换子串得到平衡字符串
- 力扣解法汇总1044-最长重复子串
- 力扣解法汇总3-无重复字符的最长子串
- LeetCode076最小覆盖子串(相关话题:双指针,滑动窗口)
- 华为OD机试 - 环中最长子串(JavaScript) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 最长连续子串(Python)| 真题+思路+考点+代码+岗位
- [LeetCode] 3. Longest Substring Without Repeating Characters 最长无重复字符的子串
- 统计子串在另一个字符中出现的次数