柱状图三分法+树状数组

柱状图

问题描述

$WTH$ 获得了一个柱状图 , 这个柱状图一共有 $N$ 个柱子

最开始第 $i$ 根柱子的高度为 $x_i$ , 他现在要将这个柱状图排成一个屋顶的形状 ,

屋顶的定义如下 :

屋顶存在一个最高的柱子 , 假设为$i$, 最终高度为 $h_i$ ,它是所有柱子之中最高的
第 $j$ 根柱子的高度为 $h_j =h_i -|i-j|$, 但这个高度必须大于 $0$, 否则就是不合法的

$WTH$ 可以对一个柱子做的操作只有将其高度加一或减一 ,

$WTH$ 正忙着享受自己的人赢生活于是他将把这个柱状图变成屋顶的任务交给了你 . 你需要求出最少进行多少次操作才能够把这个柱状图变成一个屋顶形状 .

输入

第一行包含一个正整数 $N(1 ≤ N≤ 100 000)$.

第二行包含 $N$ 个用空格隔开的正整数 , 表示 $x_i$ , 含义如题面。

输出

输出最少进行多少个操作才能够把这个柱状图变成屋顶的形状。
输入输出样例

样例 1
column.in

4
1 1 2 3

column.out

样例 2
column.in

5
4 5 7 2 2

column.out

样例的解释 :

例一升高 $2,3,4$ 号柱子一个单位高度是操作最少的方法之一,最高处为第四个柱子

例二降低第三根柱子三个高度 , 升高第四个柱子一个高度。最高处为第$ 2$ 个柱子。

数据范围

$30$%的数据满足:$1<=N<= 100$
$60$%的数据满足:$1<=N<= 5000$
$100$%的数据满足:$1<=N<=100000,1<= h_i<= 109$

分析

$20$分做法
第一层循环从$1$到$n$
第二层循环从$i$到最大值
但是因为最大值过大，这样的做法应该一分也没有
但是前几个测试点的数据比较小，因此该做法可以得到$20$分

代码

#include <bits/stdc++.h>
using namespace std;
inline int read(){
	int k = 0, f = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
	for (; isdigit(ch); ch = getchar()) k = k * 10 + ch - '0';
	return k * f;
}
const int maxn = 1e5 + 100;
int a[maxn];
int main() {
	int n = read();
	int min_ = 0x3f3f3f3f;
	for (int i = 1; i <= n; i++){
		a[i] = read();
		if(a[i] < min_)	min_ = a[i];
	}
	long long ans = 0x3f3f3f3f3f3f3f3f;
	for (int i = 1; i <= n; i++) {
		for(int height = max(i, n - i + 1); height; height++){
			long long tot = 0;
			int jl = 1;
			for (int j = 1; j <= n; j++) {
				tot += abs(height - a[j] - abs(i - j));
				if(tot > ans) break;
			}
			if(height < a[i]) jl = 0;
			ans = min(ans, tot);
			if(jl) break;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

$60$分做法
首先，最外层的循环枚举哪一根柱子是必须的
那么我们考虑决策的优化
经过证明~~（感性的理解）~~我们可以发现对于某一个特定的位置
其花费关于高度的函数是一个单峰函数
也就是说该函数存在一个最低点
所以我们可以用三分法求出函数的最低点
时间复杂度为$O(n^2logn)$
（似乎被卡掉了$5$分）

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int n,a[N],b[N];
int calc(int pos,int h){
	for(int i=1;i<=n;++i)
		b[i]=h-abs(i-pos);
	int res=0;
	for(int i=1;i<=n;++i){
		res+=abs(a[i]-b[i]);
	}
	return res;
}
int ans=0x3f3f3f3f3f3f3f3f;
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;++i)
		scanf("%lld",&a[i]);
	for(int i=1;i<=n;++i){
		int l=max(i,n-i+1),r=1e9;
		while(l <= r){
			int block=(r-l)/3;
			int m1=l+block,m2=r-block;
			if(calc(i,m1) < calc(i,m2)) r=m2-1;
			else l=m1+1;
		}
		ans=min(ans,calc(i,r));
	}
	printf("%lld\n",ans);
	return 0;
}

$100$分做法
在$60$分的做法中，我们在求函数值时会有一个$O(n)$的时间开销
现在我们考虑怎么将其优化
我们设当前最高点的坐标为$x$，改造后其高度为$h[x]$，第$i$根柱子改造前的高度为$a[i]$，改造后的高度为$h[i]$
对于某一根柱子$i$，要想形成屋顶的形状，那么必须满足$abs(h[x]-h[i])=abs(x-i)$
我们来分情况讨论：
1、如果该柱子的编号小于$x$，那么应满足$h[x]-h[i]=x-i$
则改造后的高度为$h[i]=h[x]-x+i$
如果$h[i] \geq a[i]$,变化的高度为$h[x]-x+i-a[i]$ (情况一)
如果$h[i]<a[i]$，变化的高度为$a[i]-h[x]+x-i$ （情况二）
2、如果该柱子的编号小于$x$，那么应满足$h[x]+h[i]=x+i$
则改造后的高度为$h[i]=x+i-h[x]$
如果$h[i] \geq a[i]$,变化的高度为$x+i-h[x]-a[i]$（情况三）
如果$h[i]<a[i]$，变化的高度为$a[i]-x-i+h[x]$（情况四）
那么最终的价值就是这四种情况的总和
情况一：$cnt1 \times (h[x]-x)+\sum_{i=1}^{cnt1}(i-a[i])$
情况二：$cnt2 \times (x-h[x])+\sum_{i=1}^{cnt2}(a[i]-i)$
情况三：$cnt3 \times (x-h[x])+\sum_{i=1}^{cnt3}(i-a[i])$
情况三：$cnt4 \times (h[x]-x)+\sum_{i=1}^{cnt4}(a[i]-i)$
我们发现这就是一个前缀和
因此我们想到用树状数组去优化
$cnt1$，$cnt2$，$cnt3$，$cnt4$的求解我们可以用二分去解决

代码



#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+5;
int lb(int xx){
	return xx&(-xx);
}
int n,h[maxn],rkl[maxn],rkr[maxn];
struct asd{
	int wz,val;
	asd(){}
	asd(int aa,int bb){
		wz=aa,val=bb;
	}
	bool operator < (const asd& A)const{
		return val<A.val;
	}
}jll[maxn],jlr[maxn];
struct trr{
	int sum[maxn],cnt[maxn];
}zs,ys;
struct cxtr{
	int aa,bb;
	cxtr(){
		aa=0,bb=0;
	}
};
void adz(int wz,int val,int num){
	for(int i=wz;i<=n;i+=lb(i)){
		zs.sum[i]+=val;
		zs.cnt[i]+=num;
	}
}
cxtr cxz(int wz){
	cxtr ans;
	for(int i=wz;i>=1;i-=lb(i)){
		ans.aa+=zs.sum[i];
		ans.bb+=zs.cnt[i];
	}
	return ans;
}
cxtr cxqjz(int l,int r){
	cxtr zbbf=cxz(l-1),ybbf=cxz(r),mans;
	mans.aa=ybbf.aa-zbbf.aa;
	mans.bb=ybbf.bb-zbbf.bb;
	return mans;
}
void ady(int wz,int val,int num){
	for(int i=wz;i<=n;i+=lb(i)){
		ys.sum[i]+=val;
		ys.cnt[i]+=num;
	}
}
cxtr cxy(int wz){
	cxtr ans;
	for(int i=wz;i>=1;i-=lb(i)){
		ans.aa+=ys.sum[i];
		ans.bb+=ys.cnt[i];
	}
	return ans;
}
cxtr cxqjy(int l,int r){
	cxtr zbbf=cxy(l-1),ybbf=cxy(r),mans;
	mans.aa=ybbf.aa-zbbf.aa;
	mans.bb=ybbf.bb-zbbf.bb;
	return mans;
}
int zhao(asd aa[],int val){
	int l=1,r=n,mids;
	while(l<=r){
		mids=(l+r)/2;
		if(aa[mids].val<=val) l=mids+1;
		else r=mids-1;
	}
	return r;
}
int js(int now,int gd){
	int ans=abs(h[now]-gd);
	cxtr hf;
	int wz=zhao(jll,gd-now);
	hf=cxz(wz);
	ans+=(gd-now)*hf.bb-hf.aa;
	hf=cxqjz(wz+1,n);
	ans+=hf.aa-(gd-now)*hf.bb;
	wz=zhao(jlr,gd+now);
	hf=cxy(wz);
	ans+=(gd+now)*hf.bb-hf.aa;
	hf=cxqjy(wz+1,n);
	ans+=hf.aa-(gd+now)*hf.bb;
	return ans;
}
int mans=0x3f3f3f3f3f3f3f3f;
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&h[i]);
	}
	for(int i=1;i<=n;i++){
		jll[i].wz=i;
		jll[i].val=h[i]-i;
		jlr[i].wz=i;
		jlr[i].val=h[i]+i;
	}
	sort(jll+1,jll+1+n);
	sort(jlr+1,jlr+1+n);
	for(int i=1;i<=n;i++){
		rkr[jlr[i].wz]=i;
		rkl[jll[i].wz]=i;
	}
	for(int i=1;i<=n;i++){
		ady(rkr[i],jlr[rkr[i]].val,1);
	}
	for(int i=1;i<=n;i++){
		ady(rkr[i],-jlr[rkr[i]].val,-1);
		int nl=max(i,(n-i+1)),nr=1e9,lmids,rmids,mids;
		while(nl+1<nr){
			mids=(nl+nr)>>1;
			lmids=mids-1,rmids=mids;
			int hfl=js(i,lmids),hfr=js(i,rmids);
			if(hfl>=hfr) nl=mids;
			else nr=mids;
		}
		mans=min(mans,js(i,nl));
		mans=min(mans,js(i,nr));
		adz(rkl[i],jll[rkl[i]].val,1);
	}
	printf("%lld\n",mans);
	return 0;
}

Tags: 基础--三分法数据结构--树状数组