自动搬运

查看原文

来自洛谷，原作者为

	sbno333 不进北省不改签！！！

搬运于2025-08-24 23:10:03，当前版本为作者最后更新于2025-02-21 21:43:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

中位数二分来的实惠。

考虑小于等于 $mid$ 的记作 $-1$，否则记作 $1$，我们查看此时中位数是否是 $-1$，容易证明单调性。

这有个很好的性质，就是一个这样的序列 $-1$ 是中位数，当且仅当序列和小于等于 $0$。

考虑 dp。

设 $dp_{i,c}$ 表示在 $i$ 的前缀中，每一段的中位数的和等于 $c$ 的方案数。

转移考虑枚举 $j$，表示最后一段的第一个数的下标，然后计算这一段中位数，然后把 $dp_{j-1,-n\sim n}$ 直接拿过来转移就行。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[109];
int b[109];
int n;
__int128 dp[109][209];//第二维都多加了 100，这里的 dp[i][j] 表示实际上的 dp[i][j-100}
int check(){
	dp[0][100]=1;
	for(int i=1;i<=n;i++){
		int sum;
		sum=b[i];
		for(int c=0;c<=200;c++){
			dp[i][c]=0;
		}
		for(int j=i-1;j>=0;j--){
			if(sum<=0){
				for(int c=0;c<=200;c++){
					dp[i][c]+=dp[j][c+1];
				}
			}else{
				for(int c=1;c<=200;c++){
					dp[i][c]+=dp[j][c-1];
				}
			}
			sum+=b[j];
		}
	}
	__int128 ans;
	ans=0;
	for(int i=0;i<=200;i++){
		ans+=dp[n][i]*(i<=100?-1:1);
		
	}
	return (ans<=0?-1:1);
}
signed main(){
	std::ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int l,r;
	l=1,r=1000000000;
	while(l<r){
		int mid;
		mid=l+r;
		mid>>=1;
		for(int i=1;i<=n;i++){
			b[i]=(a[i]<=mid?-1:1);
		}
		if(check()==-1){
			r=mid;
		}else{
			l=mid+1;
		}
	}
	cout<<l;
	return 0;
}

更优解

注意到这个解法的性质过于优秀，我们尝试冲击平方。

回想一下我们 DP 有哪些比较普通的优化方法。

其中一个就是拿之前做的省掉一部分工序。

什么意思？就是转移可能有重复的，我们不想重复做。

我们试试？

注意到计数器 $sum$ 变为 $0$ 时似乎情况出现了些许不同。

此时继续下去与此时的 $dp_{j,-c\sim c}$ 转移的时候是一致的。

我们可以直接省掉，把 $dp_{j,-c\sim c}$ 的成果直接拿过来。

当然别忘了特判 $j=0$，这时候的转移可不太一样。

添加这条语句。

if(sum==0&&j){
  for(int c=0;c<=200;c++){
    dp[i][c]+=dp[j][c];
  }
  break;
}

虽然复杂度没变，但是代码却有了下限，如果 $1$ 和 $-1$ 随机生成，效果会非常好。

事实上我们增加这段后时间从 $80$ 毫秒来到了 $69$ 毫秒，可以说确实有了进步。

我们继续探索，我们发现如果计数器 $sum$ 变成了 $0$，在此之前其正负性一定不变，因为之前每次就加一或者减一，然后就判定，来不及改变。

而对于正负性相同的 $sum$，我们转移是一样的啊！

所以可以直接前缀和优化这部分。

至于判断是正的还是负的，我们看 $sum$ 最开始的值即可。

不过还有个难点就是如何确定在哪个位置 $sum$ 最早取到 $0$。

我们考虑 $i$ 移动时，每次会让每个 $sum$ 都增加一个数，我们转换成 $sum$ 没加就是目标从 $0$ 转换成了另一个数。

具体的，我们维护 $jj_i$ 表示增加的数的前缀和为 $i$ 的最大的 $j$。

为啥是前缀和？这个好维护。

然后在增加一个数增加多少，指针就增加多少。

然后算上自己就行。

如下所示，第一个是维护指针，第二个算自己的语句，实际写的时候二者并不会写在一起。

当然，细节较多，别忘了 $sum$ 可能取不到 $0$。

zz+=b[i];//zz 表示指针
jj[zz]=i;

然后我们就得到了一个复杂度 $O(n^2\log n)$ 的算法。

#include<bits/stdc++.h>
using namespace std;
int a[109];
int b[109];
int n;
__int128 dp[109][209];
__int128 qz[109][209];
int jj[209];
int zz;
int check(){
	dp[0][100]=1;
	for(int i=0;i<=200;i++){
		jj[i]=-1;//sum 取不到 0 的情况认为是 -1
	}
	jj[100]=0;
	zz=100;
	qz[0][100]=1;
	for(int i=1;i<=n;i++){
		zz+=b[i];
		for(int c=0;c<=200;c++){
			dp[i][c]=0;
		}
		if(jj[zz]==-1){
			if(b[i]<=0){
				for(int c=0;c<=200;c++){
					dp[i][c]+=qz[i-1][c+1];
				}
			}else{
				for(int c=1;c<=200;c++){
					dp[i][c]+=qz[i-1][c-1];
				}
			}
		}else{
			if(b[i]<=0){
				for(int c=0;c<=200;c++){
					dp[i][c]+=qz[i-1][c+1]-qz[jj[zz]][c+1];
				}
			}else{
				for(int c=1;c<=200;c++){
					dp[i][c]+=qz[i-1][c-1]-qz[jj[zz]][c-1];
				}
			}
			for(int c=0;c<=200;c++){
				dp[i][c]+=dp[jj[zz]][c+1];
			}
			if(jj[zz]){
				for(int c=0;c<=200;c++){
					dp[i][c]+=dp[jj[zz]][c];
				}
			}
		}
		jj[zz]=i;
		for(int c=0;c<=200;c++){
			qz[i][c]=dp[i][c]+qz[i-1][c];
		}
	}
	__int128 ans;
	ans=0;
	for(int i=0;i<=200;i++){
		ans+=dp[n][i]*(i<=100?-1:1);
		
	}
	return (ans<=0?-1:1);
}
signed main(){
	std::ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int l,r;
	l=1,r=1000000000;
	while(l<r){
		int mid;
		mid=l+r;
		mid>>=1;
		for(int i=1;i<=n;i++){
			b[i]=(a[i]<=mid?-1:1);
		}
		if(check()==-1){
			r=mid;
		}else{
			l=mid+1;
		}
	}
	cout<<l;
	return 0;
}

这样我们的代码虽然常数很大，但是复杂度在那里，所以只需要跑 $20$ 毫秒，可以进入最优解第一页。

但是这道题还是受到整数类型影响，导致 $n$ 最大开到 $100$，挺可惜的。