柱狀圖三分法+樹狀數組

柱狀圖

問題描述

$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: 基礎--三分法數據結構--樹狀數組