<更新提示>
<第一次更新>
<正文>
柱状图
Description
WTH获得了一个柱状图,这个柱状图一共有N个柱子,最开始第i根柱子的高 度为xi,他现在要将这个柱状图排成一个屋顶的形状,屋顶的定义如下:
- 屋顶存在一个最高的柱子,假设为i,最终高度为hi.它是所有柱子之中最 高的.
- 第j根柱子的高度为hj=hi-|i-j|,但这个高度必须大于0,否则就是不合法的.
WTH可以对一个柱子做的操作只有将其高度加一或减一, WTH正忙着享受自 己的人赢生活于是他将把这个柱状图变成屋顶的任务交给了你.你需要求 出最少进行多少次操作才能够把这个柱状图变成一个屋顶形状.
Input Format
第一行包含一个正整数 N(1 ≤ N≤ 100 000).
第二行包含 N 个用空格隔开的正整数,表示 xi,含义如题面。
Output Format
输出最少进行多少个操作才能够把这个柱状图变成屋顶的形状。
Sample Input
5
4 5 7 2 2
Sample Output
4
解析
先考虑一下暴力思路，首先，枚举最高柱子是哪个肯定是少不了的，这个需要一重循环来枚举。对于一个最高点，如果我们知道了这个最高点的高度，我们就能依次确定其他柱子的高度，从而确定代价，就能得到最小花费。
如果直接暴力枚举最高点的高度的话，时间复杂度就是(O(n^2max{h_i}))，可以得(30)分。
考虑一下这个函数模型的数学性质：设(f(x))代表最高柱子高度为(x)时的调整所需花费。显然，当(x)取到一个恰当的值的时候，可以使得花费最小，当然，这样的值可能有很多个。但是不难发现只要任何一个其他的(x')不能取得更优的值，就可以保证这是一个单谷函数(由于相邻的柱子高度差只能为(1))。
那么就可以直接三分法枚举高度，暴力统计代价，时间复杂度(O(n^2log_2n))，可以得到(60)分。
其实这就是正解的思路，不难发现这个算法枚举和三分是少不了的，所以瓶颈就在统计花费上，如果能够快速统计花费，就可以解决本题。
注意到如下两个性质：当最高点为(i)，高度为(h_i)时，经过调整后，(forall j<i╞ h_i-i=h_j-j，forall j>i╞ h_i+i=h_j+j)。
那么利用这两个性质，我们可以把这两个关键值存起来并排序。对于一个最高点为(x)，高度为(h_x)，我们利用二分查找找到关键值(<=h_x-x)的元素在如上数组中的最大下标为(pos)，那么最高点左边调整花费可以表示为
[left [ cnt_l*(h_x-x)-sum_{i=1}^{pos}(h_i-i)
ight ] + left [ sum_{i=pos+1}^{n}(h_i-i)-cnt_r*(h_x-x)
ight ]$$，$cnt_l$代表关键值数组中关键值$<=h_x-x$且原下标小于$x$的元素的数量(**也就是说，下标不满足条件的元素我们是忽视的，$sum$中也不参与计算**)，$cnt_r$代表关键值数组中关键值$>h_x-x$且原下标小于$x$的元素的数量。
不难发现，$cnt$和$sum$都是可以表示为前缀和(部分和)结构的($cnt$即为每个符合要求的相同元素的出现次数的前缀和)，而对于新的最高点$x+1$的枚举，我们需要将相对原下标小于$x+1$的元素加入统计的范畴中，这样，涉及到插入和前缀和查询操作，我们可以用树状数组维护。
同理，对于最高点右边的调整花费，我们二分关键值$<=h_x+x$的元素在关键值数组中的最大下标$pos$，也用树状数组维护并统计即可。其计算式为$$left [ cnt_l*(h_x+x)-sum_{i=1}^{pos}(h_i+i)
ight ] + left [ sum_{i=pos+1}^{n}(h_i+i)-cnt_r*(h_x+x)
ight ]]
当然，调整最高点的花费也是需要累加的。
总的来说，我们在三分求解时利用两个树状数组来维护最高点两边的关键值，然后利用树状数组的求前缀和功能计算花费即可。
(Code:)
#include<bits/stdc++.h>
using namespace std;
#define mset(name,val) memset(name,val,sizeof name)
#define lowbit(x) ( (x) & (-x) )
#define Make(a,b) make_pair(a,b)
const int N=100070,INF=1e9;
long long n,h[N],rankl[N],rankr[N];
long long ans;
//pair -
inline pair<long long,long long> reduce(pair<long long,long long> a,pair<long long,long long> b)
{
return Make(a.first-b.first,a.second-b.second);
}
//一个点关键值及原下标
struct node
{
long long val,pos;
bool operator < (const node &t)const
{
return val < t.val;
}
};
//树状数组
struct Binary_Indexed_Tree
{
//两个值：元素出现次数的前缀和 元素值的前缀和
long long s[N],cnt[N];
//插入一个值
inline void insert(long long pos,long long val,long long num)
{
for (;pos<=n;pos+=lowbit(pos))
s[pos]+=val,cnt[pos]+=num;
}
//单点前缀和查询
inline pair<long long,long long> query(long long pos)
{
pair<long long,long long> res=Make(0LL,0LL);
for (;pos>=1;pos-=lowbit(pos))
res.first+=s[pos],res.second+=cnt[pos];
return res;
}
//区间部分和查询
inline pair<long long,long long> secquery(long long l,long long r)
{
if (l>r)return Make(0LL,0LL);
else return reduce( query(r) , query(l-1) );
}
};
node l[N],r[N];
Binary_Indexed_Tree Left,Right;
//二分查找一个节点数组中关键值<=val元素的最大下标
inline long long find(node *p,long long val)
{
long long l=1,r=n;
while ( l+1 < r )
{
long long mid=(l+r)/2;
if (p[mid].val>val)r=mid;
else l=mid;
}
if (p[r].val<=val)return r;
else if (p[l].val<=val)return l;
else return 0;
}
//计算当第x根柱子作为最高柱且高度为height时，调整柱子高度所需的花费
inline long long calc(long long x,long long height)
{
//调整最高柱子的初始花费
long long res=abs(h[x]-height);
//其他柱子关键值的前缀和查询，关键值临界点下标
pair<long long,long long> cost;long long pos;
//计算最高柱子左边的花费
//找到小于等于关键值的最大下标
pos=find(l,height-x);
//查询前缀和
cost=Left.query(pos);
//计算花费
res += (height-x)*cost.second*1LL - cost.first;
//查询右边的部分和
cost=Left.secquery(pos+1,n);
//计算花费
res += cost.first - (height-x)*cost.second*1LL;
//同理，计算最高柱子右边的花费
pos=find(r,height+x);
cost=Right.query(pos);
res += (height+x)*cost.second*1LL - cost.first;
cost=Right.secquery(pos+1,n);
res += cost.first - (height+x)*cost.second*1LL;
return res;
}
inline void input(void)
{
scanf("%lld",&n);
for (int i=1;i<=n;i++)
scanf("%lld",&h[i]);
}
inline void init(void)
{
//建立l，r两个储存关键值的数组
for (int i=1;i<=n;i++)
l[i]=(node){h[i]-i,i},r[i]=(node){h[i]+i,i};
//按照关键值排序
sort(l+1,l+n+1);
sort(r+1,r+n+1);
ans=LONG_LONG_MAX;
//键入原下标，得到排序后的排名(排序后的新下标)
for (int i=1;i<=n;i++)
rankl[ l[i].pos ] = i , rankr[ r[i].pos ] = i;
}
inline void solve(void)
{
//先将所有柱子加入右树状数组中
for (int i=1;i<=n;i++)
Right.insert( rankr[i] , r[ rankr[i] ].val , 1 );
//枚举最高柱子
for (int i=1;i<=n;i++)
{
//先将自己删除
Right.insert( rankr[i] , -r[ rankr[i] ].val , -1 );
//三分高度
long long lbound=max(i*1LL,(n-i+1)*1LL),ubound=INF;
while ( lbound+1 < ubound )
{
long long mid=(lbound+ubound)/2;
long long lmid=mid-1,rmid=mid;
long long lcost=calc(i,lmid),rcost=calc(i,rmid);
//找单谷函数极小值点
if (lcost>=rcost)lbound=mid;
else ubound=mid;
}
//避免误差，左右边界相邻并退出循环时，利用左右端点分别更新一次答案
ans = min(ans,calc(i,lbound));
ans = min(ans,calc(i,ubound));
//将这个处理好的点压入左边的树状数组中
Left.insert( rankl[i] , l[ rankl[i] ].val , 1 );
}
}
int main(void)
{
freopen("column.in","r",stdin);
freopen("column.out","w",stdout);
input();
init();
solve();
printf("%lld
",ans);
return 0;
}
<后记>