当前位置: 首页 > ds >正文

M - 中位数

Description

给定一个长度为 NN 的非负整数序列 AA,对于前奇数项求中位数。

Input

第一行一个正整数 NN。

第二行 NN 个正整数 A1…NA1…N​。

Output

共 ⌊N+12⌋⌊2N+1​⌋ 行,第 ii 行为 A1…2i−1A1…2i−1​ 的中位数。

Sample 1

InputcopyOutputcopy
7
1 3 5 7 9 11 6
1
3
5
6

Sample 2

InputcopyOutputcopy
7
3 1 5 9 8 7 6
3
3
5
6

Hint

对于 20%20% 的数据,N≤100N≤100;

对于 40%40% 的数据,N≤3000N≤3000;

对于 100%100% 的数据,1≤N≤1000001≤N≤100000,0≤Ai≤1090≤Ai​≤109。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int n;
int main() {ios::sync_with_stdio(false);        // 禁用同步cin.tie(nullptr);                   // 解除cin与cout绑定cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}vector<int> m;for (int i = 1; i <= n; i ++) {if (i == 1) {m.insert(m.begin(), a[i]);}else {int x = 0, y = m.size();while (x < y) {int mid = (x + y) / 2;if (m[mid] > a[i]) {y = mid;}else {x = mid + 1;}}m.insert(m.begin() + x, a[i]);}if (i % 2 == 1) {cout << m[m.size() / 2] << endl;}}return 0;
}

http://www.xdnf.cn/news/14091.html

相关文章:

  • Android 实体键盘 设置默认布局
  • 【舞蹈】FineDance
  • 新一代python管理工具--uv
  • Rust 学习笔记1
  • 数字孪生系统汽车工厂生产异常监控的智能利器
  • 快速解决软件测试的逻辑方法运用
  • 数字孪生之KTV洗脚城白皮书:娱乐产业的虚实融合革命
  • LX-YST-1
  • Qt背景平铺
  • Java-45 深入浅出 Tomcat 核心架构与处理流程全解析Coyote IO模型与协议
  • java集合(十) ---- LinkedList 类
  • 基于CT图像的硬参数共享多任务分析:肝脏肿瘤分割与良恶性分类
  • ELK 日志分析系统
  • transformer demo
  • 深入剖析Redis Cluster集群,Redis持久化机制,Redis数据类型及其数据结构
  • DeepSeek与呼叫中心系统结合提升效率
  • ELK日志文件分析系统——1
  • 美化显示MSVC调试的数据结构
  • 当雷达学会“读心术” 汽车舱内安全迈入新纪元
  • C盘瘦身?
  • 如何将视频从 iPhone 传输到 HP 笔记本电脑
  • Untiy打包安卓踩坑
  • 单点登录(SSO)技术原理与实现指南
  • 【Docker基础】Docker核心概念:命名空间(Namespace)详解
  • C++11 Generalized(non-trivial) Unions:从入门到精通
  • LINUX613计划测put
  • Hadoop 003 — JAVA操作MapReduce入门案例
  • 传统数据仓库正在被 Agentic AI 吞噬?Agentic Data Stack 初探
  • 代码训练LeetCode(33)字符串首次匹配
  • 基于Cesium的Shadertoy纹理材质应用