[***]HZOJ 柱状图

神仙题。

作者的正解：

算法二：对于60%的数据：考虑直接枚举屋顶的位置,总花费与屋顶的高度的关系是一个单峰函数,,我们可以用三分法三分屋顶的高度. 时间复杂度O(n²*logn)。

算法三：对于100%的数据： 我们枚举屋顶位置再三分高度的做法，复杂度的瓶颈在于花费的计算。假设屋顶在i处,高度为h_i,如果j<i,有h_j-j=h_i-i ; 如果j>i,有h_j+j=h_i+i。

根据权值排序，建立树状数组来解决权值与i的权值的关系，用两个树状数组维护。时间复杂度O(n(logn)(logv),V为屋顶的高度。

对于60%的数据大概有两种做法：

1.如作者题解，说的挺清楚的。

2.考虑对于一个确定的位置作为屋顶，那么屋顶的高度是确定的，证明以后再说。将每个点的高度加上到屋顶的距离，高度为之后序列的中位数，所以就可以模拟退火了。

对于100%的数据：

1.模拟退火（没脸）。

2.枚举屋顶，三分高度，然后主要的优化就是在计算花费上。可以用两个树状数组维护。

由于时间比较紧剩下的先咕掉了……

 #include<algorithm>

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #define int LL

 #define LL long long

 #define MAXN 100010

 #define reg register

 #define con const

 using namespace std;

 struct node

 {

     int val,id;

     friend bool operator < (node a,node b)

     {return !(a.val^b.val)?a.id<b.id:a.val<b.val;}

 }al[MAXN],ar[MAXN];

 int n,a[MAXN],maxh,rkl[MAXN],rkr[MAXN];

 #define lowbit(x) ((x)&(-(x)))

 struct bit

 {

     int C[MAXN],num[MAXN];

     void add(reg int x,reg con int y,reg con int z)

     {while(x<=n){C[x]+=y;num[x]+=z;x+=lowbit(x);}}

     pair<int,int> ask(reg int x)

     {

         int sum=,nnum=;

         while(x)

         {

             sum+=C[x];

             nnum+=num[x];

             x-=lowbit(x);

         }

         return make_pair(sum,nnum);

     }

 }le,re;

 __attribute((always_inline))int get(reg con int x,reg con int maxh)

 {

     int ans=;

     ans+=abs(maxh-a[x]);

     int pos=upper_bound(al+,al+n+,(node){maxh-x,x})-al-;

     pair<int,int> tem=le.ask(pos);

     ans+=tem.second*(maxh-x)-tem.first;

     pair<int,int> tem2=le.ask(n);

     ans+=tem2.first-tem.first-(tem2.second-tem.second)*(maxh-x);

     pos=upper_bound(ar+,ar+n+,(node){maxh+x,x})-ar-;

     tem=re.ask(pos);

     ans+=tem.second*(maxh+x)-tem.first;

     tem2=re.ask(n);

     ans+=tem2.first-tem.first-(tem2.second-tem.second)*(maxh+x);

     return ans;

 }

 __attribute((always_inline))void read(int &s)

 {

     s=;

     reg int f=;reg char a=getchar();

     while(a<''||a>''){if(a=='-')f=-;a=getchar();}

     while(a>=''&&a<=''){s=s*+a-'';a=getchar();}

     s*=f;

 }

 signed main()

 {

     read(n);

     int ans=0x7ffffffffffff;

     for(reg int i=;i<=n;++i)

     {

         read(a[i]);

         al[i].val=a[i]-i,al[i].id=i;

         ar[i].val=a[i]+i,ar[i].id=i;

     }

     sort(al+,al+n+);

     sort(ar+,ar+n+);

     for(reg int i=;i<=n;++i)rkl[al[i].id]=i,rkr[ar[i].id]=i;

     for(reg int i=;i<=n;++i)re.add(rkr[i],a[i]+i,);

     for(reg int i=;i<=n;++i)

     {

         re.add(rkr[i],-a[i]-i,-);

         int l=max(i,n-i+),r=1e9,ml,mr;

         ans=min(ans,get(i,l));

         while(r>l+)

         {

             int mid=(l+r)>>;

             ml=mid-,mr=mid;

             int ans1=get(i,ml),

                 ans2=get(i,mr);

             if(ans1<ans2)r=mid;

             else l=mid;

             ans=min(ans,ans1);

             ans=min(ans,ans2);

             if(!(ml^l)&&!(mr^r))break;

         }

         le.add(rkl[i],a[i]-i,);

     }

     printf("%lld\n",ans);

 }

巴特西

[***]HZOJ 柱状图

最新文章

热门文章