首页 > 其他分享 >【洛谷】P1168 中位数 的题解

【洛谷】P1168 中位数 的题解

时间:2024-09-26 20:48:30浏览次数:11  
标签:洛谷 int 题解 long 插入 num read P1168

【洛谷】P1168 中位数 的题解

题目传送门

题解

不懂就问,这是什么标签啊,《线段树》《二分》《堆》《树状数组》qaq

谔谔,教练讲的这是一题线段树,看半天看不出来,也不会做,只好去看题解。其他的题解讲什么主席树,平衡树,分块,结果看完第一篇人都傻了。什么东西嘛qaq(恼

vector 直接一波好吧。

保证每次插入的时候原序列有序。所以用一个二分查找找到插入的位置插入就行了。

因为每次插入后排序时间代价太大,则插入采用 upper_bound 来二分大于等于该数的数的指针,使得每次插入完都是已经排好序

然后每次插入后,直接输出当前容器内第 $\frac{size() - 1}{2} $项即可

理论时间复杂度 O ( n 2 log ⁡ n ) O(n^2\log n) O(n2logn),但是常数极小,而且跑不满,再加个快读快写就行,甚至 scanfprintf 都行。

当然啦,不太建议这种水过去的作法qaq。

代码

#include <bits/stdc++.h>
#define lowbit(x) x & (-x)
#define endl "\n"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
namespace fastIO {
	inline int read() {
		register int x = 0, f = 1;
		register char c = getchar();
		while (c < '0' || c > '9') {
			if(c == '-') f = -1;
			c = getchar();
		}
		while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
		return x * f;
	}
	inline void write(int x) {
		if(x < 0) putchar('-'), x = -x;
		if(x > 9) write(x / 10);
		putchar(x % 10 + '0');
		return;
	}
}
using namespace fastIO;
int n;
vector<int> a;
int main() {
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	n = read();
	for(int i = 1; i <= n; i ++) {
		int num;
		num = read();
		a.insert(upper_bound(a.begin(), a.end(), num),num);
		if(i % 2 == 1) {
			write(a[(i - 1) / 2]), putchar('\n');
		}
	}
	return 0;
}

标签:洛谷,int,题解,long,插入,num,read,P1168
From: https://blog.csdn.net/ZH_qaq/article/details/142566965

相关文章

  • 洛谷题单指南-分治与倍增-P4155 [SCOI2015] 国旗计划
    原题链接:https://www.luogu.com.cn/problem/P4155题意解读:在m个点的环上,有n个区间,且各个区间之间没有包含关系,计算从每个区间开始,最少要多少个区间能覆盖环上所有m个点。解题思路:本质上是一个区间覆盖问题!1、破环成链由于题目中是一个环,对于环的问题,在区间DP中介绍过,经典处理......
  • CF1063E Lasers and Mirrors题解
    一道很好的手玩题,被薄纱了。首先判掉\(\foralli,p_i=i\)的情况(显然是\(n\))然后考虑按照\(p_i\)连边,先构造每一个环的方案。发现可以简单放置两面镜子使得\(i\)射到\(p_i\),而且只要从高到底构造,一定不会产生影响。但是每一个环的最后一个点很特殊,因为第1个点下面放置了让第1个......
  • LOJ 6241. 性能优化 I 题解
    题给代码意为\[\begin{align*}&\sum\limits_{i=1}^n\sum\limits_{j=1}^{\lfloor\fracni\rfloor}\sum\limits_{k=1}^j[\gcd(j,k)=1]\\=&\sum\limits_{i=1}^n\sum\limits_{j=1}^{\lfloor\fracni\rfloor}\varphi(j)\\......
  • P8475 「GLR-R3」雨水 题解
    关于这道题目卡\(O(n\logn)\)但是放\(O(n^2)\)我也是很疑惑。我们发现,题目要求的是字典序最小的序列。但凡涉及了字典序最小,答案或多或少的都会带点贪心思想。那我们也来贪一贪。考虑当前枚举到第\(i\)个点,如果后面有比它更小的数,那显然把它们交换过来是更优的。如果有多......
  • P8474 「GLR-R3」立春 题解
    俗话说的好:“打表出奇迹”,所以我们这一题打表计算。其实确实可以打表来找规律。通过打表,我们可以获得如下的结果:1 12 33 214 3155 9765…… ……然后观察可得:\[1\times3=1\times(2^2-1)=3\]\[3\times7=3\times(2^3-1)=21\]\[21\times15=21\t......
  • Codeforces Round 971 (Div. 4)题解记录(G3待补)
    A.Minimize!暴力模拟一遍即可#include<iostream>#include<queue>#include<deque>#include<map>#include<set>#include<stack>#include<vector>#include<bitset>#include<math.h>#include<random>#include&l......
  • P8563 Magenta Potion 题解
    前排警告这是较为通用,不需要脑子,但是代码量巨大的题解,请谨慎食用解题思路不知道大家做没做过带修改的区间最大连续子段和,这一题其实就是带修改的区间最大连续子段积。那么其实做法是类似的。我们用线段树维护五个量:当前区间答案,区间前缀最小值,区间前缀最大值,区间后缀最小值,区......
  • P8564 ρars/ey 题解
    显然树上背包。首先一眼会想到的状态:\(dp_{i,j}\)表示\(i\)的子树最后剩下\(j\)个结点的最小代价。然而开始写会发现这并不好DP。于是我们换一个想法:\(dp_{i,j}\)表示\(i\)的子树删去\(j\)个结点的最小代价。则有转移方程:\[dp_{i,j}=\min_{v\inson(i)}\{dp_{i......
  • 题解:UVA1456 Cellular Network
    UVA1456CellularNetwork题解夭寿了!30行写完紫题了!更新:已联系管理员修改难度,现在是绿题题意很简单,不再赘述。首先一个小贪心,将概率\(u​\)进行从大到小的排序,优先查看概率大的区域,显然这样能够保证访问数量期望最小。接着考虑如何将区域分组。一个显而易见的思路是动态......
  • 题解:CF437B The Child and Set
    CF437BTheChildandSet题解这题目就一个问题。啥是\(\operatorname{lowbit}\)?\(\operatorname{lowbit}(x)\)是指\(x\)的二进制表示中最低位的\(1\)所表示的值。例如\((14)_{10}=(1110)_2\),其中最低位的\(1\)在第二位,表示\((2)_{10}\),即\(\operatorname{lo......