当前位置:网站首页>【集训DAY3】中位数
【集训DAY3】中位数
2022-08-09 22:35:00 【VL——MOESR】
思路:
从中间往左扫
我们用一个桶存它比他大的个数出现的次数
然后在往右扫统计答案
c o d e code code
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN = 1e5 + 10;
int n, b;
int a[MAXN], g[2][MAXN * 2];
int ans;
int main() {
scanf("%d%d", &n, &b);
int p = 0;
for(int i = 1; i <= n; i ++) {
scanf("%d", &a[i]);
if(a[i] == b) p = i;
}
int tmp = 0;
for(int i = p; i >= 1; i --) {
if(a[i] < a[p]) tmp ++;
else tmp --;
g[(p - i) % 2][tmp + MAXN] ++;
}
tmp = 0;
for(int i = p; i <= n; i ++) {
if(a[i] > a[p]) tmp ++;
else tmp --;
ans += g[(i - p) % 2][tmp + MAXN];
}
printf("%d", ans);
return 0;
}
边栏推荐
- [JZOF] 82 binary tree with a path of a certain value (1)
- 2022-08-09 mysql/stonedb-慢SQL-Q16分析
- 【诗歌】最高级的惩罚就是沉默
- 什么是平面文件数据库? 如何导入多种格式的文件:DSV、JSON、XML?
- What are the basic steps to develop a quantitative trading strategy?
- 全球不用交税的国家,为什么不交
- Sqlserver限制账户在哪些ip下才可以访问数据库
- 【接口测试】requests 库请求体字符串解码
- 直播app开发搭建,flutter 实现自适应、自动换行、相对布局
- 2020年度SaaS TOP100企业名单
猜你喜欢
2022-08-09 mysql/stonedb-慢SQL-Q16分析
Qt 之 QDateEdit 和 QTimeEdit
How to match garbled characters regularly?
&& 不是此版本的有效语句分隔符
【面试高频题】可逐步优化的链表高频题
探索TiDB Lightning源码来解决发现的bug
ABAP中Collect的用法
直播预告 | ICML 2022 11位一作学者在线分享神经网络,图学习等前沿研究
Gartner's global integrated system market data tracking, hyperconverged market growth rate is the first
一体化伺服电机在三轴钻孔机中的应用
随机推荐
【诗歌】最高级的惩罚就是沉默
[Cloud Native] This article explains how to add Tencent Crane to Kubevela addon
安踏携手华为运动健康共同验证冠军跑鞋 创新引领中国体育
Interfering with BGP routing---community attributes
后台管理实现导入导出
tiup cluster stop
JS基础笔记-关于对象
JS--popstate事件--使用/教程/实例
ALV报表总结2022.8.9
CMake使用记录
力扣:474.一和零
【JZOF】32从上往下打印二叉树
Day 12 of learning to program
61.【快速排序法详解】
五分钟商学院(基础---商业篇)
String类常用方法
2022-08-09 mysql/stonedb-慢SQL-Q16分析
【面试高频题】可逐步优化的链表高频题
&& 不是此版本的有效语句分隔符
iNFTnews | 迪士尼如何布局Web3