专栏文章

题解：P13091 中位数

IIgunareo
P13091题解参与者 5已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@mioyz9s6
此快照首次捕获于
2025/12/03 03:27
3 个月前
此快照最后确认于
2025/12/03 03:27
3 个月前
查看原文

思路

显然的，如果可以最终答案为 ii，那么对于任意 1≤j≤i1\le j\le i，一定存在解使得答案 ans≥jans\ge j，故本题答案满足单调性。
考虑二分答案，则需要判断是否可以使答案 ans≥midans\ge mid，可以将该问题转化为如下方式解决：
将原数组转化为一个 0101 序列，对于 ai≥mida_i\ge mid 使得 ai←1a_i\gets 1，否则对于 ai<mida_i< mid 使得 ai←0a_i\gets 0，那么原问题变为能否使该序列答案为 11。
相邻数才能合并，所以需要维护一个栈，依次从栈顶加入元素进行处理。
对于连续三个数消去的情况进行分类讨论：
  1. 三个数为 000000，删去后变为 00，减少两个 00，故删去一定不劣。
  2. 三个数为 001001，010010，011011，100100，101101，110110 六种情况，可以发现此类情况删去后数列中 11 和 00 减少数量相同，故最后需要比较两者数量多少判断情况可行性，谁多剩下谁。
  3. 三个数为 111111，删去少两个 11 一定不优，不删等待后续计算。
根据以上结论 11 将序列中的所有 000000 合并，则序列中连续 00 的长度不超过 22。
但是此时直接使用结论 22 比较 0,10,1 数目是错误的，因为存在诸如 0010000100 的情况，消去中间的 11 后还会出现 000000，直接计算会产生错误。
所以对于 001001 的情况也需要直接合并处理，情况 22 其他 55 种则不需要改变，况且后续情况不明，合并不一定优（比如又接上两个 00 什么的都有可能）。
然后根据比较合并后整个序列中 0,10,1 数目大小即可判断是否存在 ans≥midans\ge mid。
还有别忘了多测清空。

代码实现

代码不长，私以为我的码风还是比较朴素正统的，可读性较强，应该方便理解。
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int x[100005],y[100005],Q[100005],tail=0,n;
bool check(int u){
	tail=0;
	for(int i=1;i<=n;i++){
		if(x[i]>=u)y[i]=1;
		else y[i]=0;
	}
	for(int i=1;i<=n;i++){
		if(tail>1&&Q[tail]==0&&Q[tail-1]==0)tail--;//001 和 000 的前缀都是 00 就合并处理了
		else Q[++tail]=y[i];
	}
	int summ=0;
	for(int i=1;i<=tail;i++){
		if(Q[i]==1)summ++;
		else summ--;
	}//统计数目遇 0 减一，遇 1 加一，总数为正则 1 比 0 多
	return summ>0;//长度奇数不存在总和为 0
}
signed main(){
	int T;
	scanf("%lld",&T);
	while(T--){
		scanf("%lld",&n);
		for(int i=1;i<=n;i++)scanf("%lld",&x[i]);
		int l=1,r=1e9;
		while(l<r){
			int mid=(l+r+1)/2;
			if(check(mid))l=mid;
			else r=mid-1;
		}
		printf("%lld\n",l);
	}
	return 0;
}

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...