当前位置:网站首页>【集训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;
}
边栏推荐
- 基于 RocksDB 实现高可靠、低时延的 MQTT 数据持久化
- 干货!迈向鲁棒的测试时间适应
- 测试2年,当时身边一起入行的朋友已经月薪20k了,自己还没过万,到底差在了哪里?
- 【哲理】读书的意义
- 68.qt quick-qml多级折叠下拉导航菜单 支持动态添加/卸载 支持qml/widget加载等
- 【JZOF】77按之字形打印二叉树
- kubesphere
- Live Preview | ICML 2022 11 first-author scholars share online neural network, graph learning and other cutting-edge research
- Gartner's global integrated system market data tracking, hyperconverged market growth rate is the first
- Leetcode 235. 二叉搜索树的最近公共祖先
猜你喜欢
随机推荐
集合运算样例
新增一地公布2022下半年软考报考时间
CAD 绘制圆角处理
k8s部署mysql
YGG 经理人杯总决赛已圆满结束,来看看这份文字版总结!
领跑政务云,连续五年中国第一
国内BI厂商一览
如何知道电脑开机记录?
harbor配置远程仓库
【接口测试】requests 库请求体字符串解码
软考 --- 软件工程(7)软件项目管理(下)
用函数统计最长单词的字母数量
Snap: 322. Change of Change
IT传奇人物菲尔德的转型经验教训及给CIO的建议
微信小程序获取微信用户步数
友元类和友元函数
Mysql集群 ShardingSphere
MQTT X Web:在线的 MQTT 5.0 客户端工具
Comprehensive analysis of FPGA basics
70. 爬楼梯进阶版









