题解 P6874 [COCI2013-2014#6] KOCKICE

· · 题解

题目传送门

更好的阅读体验

算法分析：二分

提供一种基于二分的算法。

注意一下坑点：

下面来分析一下如何二分。

这里二分不直接二分答案。如果直接二分答案，并没有把原问题变成更简单的子问题。而二分的核心在于将复杂的原问题转化为较简单的子问题。因此，我们二分中间列的高度。

单调性在哪里？由于相邻的砖头高度恰相差 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;
}

AC

欢迎交流讨论，请点个赞哦~