算法分析：二分
提供一种基于二分的算法。
注意一下坑点：
- 最低那一列就是正中间那一列。
- “最低的列左右两侧的砖头数量必须相同”指的不是与中间列相邻的两列，而是所有对应的列。
下面来分析一下如何二分。
这里二分不直接二分答案。如果直接二分答案，并没有把原问题变成更简单的子问题。而二分的核心在于将复杂的原问题转化为较简单的子问题。因此，我们二分中间列的高度。
单调性在哪里？由于相邻的砖头高度恰相差 \(1\)，中间列高度确定时其他列的砖头数量也能确定。因此，若中间列高度继续增加 \(1\) ，可以依此判断出总操作次数的变化情况。假设当前中间列高度为 \(mid\)，那么第 \(i\) 列的目标高度为 \(x=mid+\left \vert n/2-i+1\right \vert\)。若中间列继续增加 \(1\)，那么将有 \(res=\sum\limits_{i=1}^n (a_i \ge x)+(b_i \ge x)\) 列砖头的操作次数将减 \(1\) ，\(2\times n-res\) 列砖头操作次数将增加 \(1\)。随着 \(mid\) 的增大，\(res\) 呈现出单调递减的特征，符合了二分的单调性要求。当 \(res \ge n\) 时，当前 \(mid\) 的是一个可行解。在求出中间列的最佳高度之后，暴力计算求出答案即可。
关于时间复杂度，检查可行性为\(\mathcal{O}(n)\)，因此二分时间复杂度为 \(\mathcal{O}(n\log_2(n))\)。最后计算答案为 \(\mathcal{O}(n)\)。因此总体时间复杂度为 \(\mathcal{O(n\log_2(n))}\)。
下面给出代码：
#include<bits/stdc++.h>
#define ll long long
#define reg register
#define F(i,a,b) for(reg int i=a;i<=b;++i)
using namespace std;
inline ll read();
const int N=3e5+10;
int n,a[N],b[N];
ll ans,sum;
inline bool check(ll mid) {
int res=0;
F(i,1,n){
ll x=mid+abs(n/2+1-i);
res+=(a[i]>=x)+(b[i]>=x);//计算操作次数将-1的列数
}
return res>=n;
}
int main() {
n=read();
ll l=0,r=0;
F(i,1,n)a[i]=read(),r=max(r,(ll)a[i]);
F(i,1,n)b[i]=read(),r=max(r,(ll)b[i]);
while(l<=r){//二分
ll mid=l+r>>1ll;
check(mid)?l=mid+1,ans=mid:r=mid-1;
}
F(i,1,n){//统计答案
ll x=ans+abs(n/2+1-i);
sum+=abs(a[i]-x)+abs(b[i]-x);
}
printf("%lld",sum);
return 0;
}
inline ll read() {
reg ll x=0;
reg char c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c))x=(x<<1ll)+(x<<3ll)+(c^48),c=getchar();
return x;
}
欢迎交流讨论，请点个赞哦~