自动搬运

查看原文

来自洛谷，原作者为

	Find_Yourself 竹杖芒鞋轻胜马，谁怕？一蓑烟雨任平生。

搬运于2025-08-24 22:48:10，当前版本为作者最后更新于2023-06-01 21:41:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

不难推理出当初始绳长为 $len$，需要下降的距离为 $d$，并且满足 $d\le len<2d$ 时，最优的环套法可以只损失 $2d-len$ 长度的绳子，留下 $2(len-d)$ 的绳子。

当 $2d\le len$ 时存在一种不损耗绳长的方法可以下到下一根钢管，即把整根绳子系成一个环，到达下面再剪断。

正文：

线段树优化 DP。

我们先将所有钢管按高度从大到小排序，如果高度相同则按权值从小到大排序。

然后将权值离散化，对于相同的 $v$，给 $h$ 更大的赋更小的值。

考虑从低往高 DP。

定义 $f_i$ 表示最初站在 $i$ 号钢管，至少需要多长的绳子才能下到地面。

转移方程如下：

$$f_{i}=\begin{cases}f_j&2(h_i-h_j)\le f_j\land v_j\ge v_i\\h_i-h_j+\frac{f_j}{2}&2(h_i-h_j)>f_j\land v_j\ge v_i\end{cases} $$

开两棵线段树，第一棵 $t_1$ 维护 $\min(f_j)(h_j+\frac{f_j}{2}\ge h_i)$，第二棵 $t_2$ 维护 $\min(-h_j+\frac{f_j}{2})(h_j+\frac{f_j}{2}<h_i)$，每次分别在两棵线段树上查询 $[v_i+1,n]$ 内的最小值，记为 $m_1,m_2$。那么 $f_{i}=\min(m_1,m_2+h_i)$。

容易发现，一根钢管的贡献是有范围的。

对于钢管 $j$，我们二分出离它最远的 $i$，满足 $h_i\le h_j+\frac{f_j}{2}$，那么 $[i,j)$ 这些位置都可以通过第一种转移被 $f_j$ 贡献到，$[1,i)$ 这些位置可以通过第二种转移被 $h_i-h_j+\frac{f_j}{2}$ 贡献到。

具体的，我们假设二分到的位置为 $w$，那么在 $w-1$ 处标记编号 $j$，遍历到这里时，将 $t_1$ 对应位置改为 $\inf$，$t_2$ 对应位置改为 $-h_j+\frac{f_j}{2}$，更新一下线段树即可。

这里之所以可以通过赋值 $\inf$ 来撤销，是因为离散化后已经保证 $v_i$ 互不相同了。

注意，由于 $h$ 在 $10^{18}$ 级别，如果用 double 会爆精度并喜提 $0$ 分，所以要用 long double。

如果你还不放心，可以在每次除以 $2$ 后向上取整，至于为什么对，这里有具体证明。

我们之所以不考虑正着推（从上往下），是因为多一个二分带来的 $\log$，而且转移时分三段，写起来极其麻烦。

综上，复杂度 $O(n\log n)$，代码很短。

code:

#include<bits/stdc++.h>
#define ls (id*2)
#define rs (id*2+1)
using namespace std;
typedef long long ll;
const ll N=5e5+5,inf=LLONG_MAX>>2;
ll n,f[N],p;
vector<int>vec[N];
struct node{ll h,v;}a[N];
bool cmph(node x,node y){return x.h!=y.h?x.h>y.h:x.v<y.v;}
bool cmpv(node x,node y){return x.v!=y.v?x.v<y.v:x.h>y.h;}
struct tree{
  ll mi[4*N];
  void change(int id,int l,int r,int x,ll k){
    if(l==r){mi[id]=k;return;}
    int mid=(l+r)>>1;
    if(x<=mid)change(ls,l,mid,x,k);
    else change(rs,mid+1,r,x,k);
    mi[id]=min(mi[ls],mi[rs]);
  }
  ll query(int id,int l,int r,int L,int R){
    if(l==L&&r==R)return mi[id];
    int mid=(l+r)>>1;
    if(R<=mid)return query(ls,l,mid,L,R);
    else if(L>mid)return query(rs,mid+1,r,L,R);
    else return min(query(ls,l,mid,L,mid),query(rs,mid+1,r,mid+1,R));
  }
}t,t2;
inline void get(int id){
  int l=1,r=id,ans;
  while(l<=r){
    int mid=(l+r)>>1;
    if(a[mid].h<=a[id].h+(f[id]>>1))ans=mid,r=mid-1;
    else l=mid+1;
  }
  t.change(1,1,p,a[id].v,f[id]);
  vec[ans-1].push_back(id);
}
int main(){
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cin>>n;p=n;
  for(int i=1;i<=n;++i)cin>>a[i].h>>a[i].v;
  sort(a+1,a+n+1,cmpv);
  for(int i=1;i<=n;++i)a[i].v=i;
  sort(a+1,a+n+1,cmph);a[n+1].v=++p;
  for(int i=1;i<=4*p;++i)t.mi[i]=t2.mi[i]=inf;
  get(n+1);
  for(int i=n;i>=1;--i){
    for(int j=0;j<vec[i].size();++j){
      int id=vec[i][j];
      t.change(1,1,p,a[id].v,inf);
      t2.change(1,1,p,a[id].v,-a[id].h+((f[id]+1)>>1));
    }
    f[i]=inf;
    f[i]=min(f[i],min(t.query(1,1,p,a[i].v+1,p),t2.query(1,1,p,a[i].v+1,p)+a[i].h));
    get(i);
  }
  cout<<f[1]<<endl;
  return 0;
}