提供一个不用二分的做法。

将问题拆成上架厚度 $u$ 和下架厚度 $d$ 两部分。最少打磨次数等价于最大化最终统一总厚度 $h$，因此需要在不超初始值和满足相邻差 $\le x$ 的前提下，让每本上架书尽量厚。

贪心思路：当前最薄的那本上架书已经不可能再被削薄，于是以它为基准，向两侧传递限制——如果邻居比它厚超过 $x$，就砍到恰好 $U_i+x$。用优先队列不断取出当前最小值，调整邻居后重新入队，直到所有相邻差都合法，得到上架的最厚可行序列 $U_i$。

最后统一高度取所有 $U_i+d_i$ 的最小值作为 $h$，答案即为 $\sum (u_i+d_i) - n \cdot h$。

理论复杂度 $O(n \log n)$，优于二分的 $O(n \log V)$。

代码：

#include<bits/stdc++.h>
#define int long long
#define rep(i,l,r,x) for(int i=(l);i<=(r);i+=(x))
#define per(i,r,l,x) for(int i=(r);i>=(l);i-=(x))
#define pr pair<int,int>
#define fr first
#define sc second
using namespace std;
const int N=1e6+5,INF=1e18;
int n,x,minn=INF,ans;
int u[N],d[N];
bool vis[N];
priority_queue<pr,vector<pr>,greater<pr>> q;
signed main() {
	freopen("book.in","r",stdin);
	freopen("book.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>x;
	rep(i,1,n,1) {
		cin>>u[i]>>d[i];
		q.push({u[i],i});
	}
	while(!q.empty()) {
		int id=q.top().sc;
		q.pop();
		if(vis[id])continue;
		vis[id]=1;
		if(id>1) {
			if(u[id-1]>u[id]+x) {
				int cha=u[id-1]-u[id]-x;
				u[id-1]-=cha;
				ans+=cha;
			}
			q.push({u[id-1],id-1});
		}
		if(id<n) {
			if(u[id+1]>u[id]+x) {
				int cha=u[id+1]-u[id]-x;
				u[id+1]-=cha;
				ans+=cha;
			}
			q.push({u[id+1],id+1});
		}
	}
	rep(i,1,n,1)minn=min(minn,u[i]+d[i]);
	rep(i,1,n,1) {
		if(u[i]+d[i]>minn)ans+=u[i]+d[i]-minn;
	}
	cout<<ans;
	return 0;
}

提供一个二分的代码。

注意到 最终答案（以下记作 $ans$）越小，$h$ 越大，考虑二分。

二分 $h$，判断该种情况是否存在。

每次求出 $a_i$ 的可能的最大值和最小值，记作 $r_i$ 和 $l_i$，可得 $[l_i,r_i]$ 为 $a_i$ 的存在区间。注意到 $a_{i-1}$ 的存在区间和 $x$ 会影响 $a_i$ 的存在区间，通过判断枚举更改即可。

考场代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,inf=2e9+10;
int n,x,h=inf;
struct node{
	int a,b;
}a[N];
int r[N],l[N];
int sum;
bool check(int mid){ //a+b=mid
//	cout<<"check:"<<mid<<"\n";
	for(int i=1;i<=n;i++) l[i]=r[i]=0;
	for(int i=1;i<=n;i++){
		if(a[i].a+a[i].b==mid){
			r[i]=l[i]=a[i].a;
		}else if(a[i].a>=mid){
			r[i]=mid;
			if(a[i].b>=mid){
				l[i]=0;
			}else{
				l[i]=mid-a[i].b;
			}
		}else{//a[i].a<mid
			r[i]=a[i].a;
			if(a[i].b>=mid){
				l[i]=0;
			}else{
				l[i]=mid-a[i].b;
			}
		}
	}
//	cout<<"l:";
//	for(int i=1;i<=n;i++) cout<<l[i]<<" "; 
//	cout<<"\n";
//	cout<<"r:";
//	for(int i=1;i<=n;i++) cout<<r[i]<<" "; 
//	cout<<"\n";
	for(int i=2;i<=n;i++){
		if(l[i]>r[i-1]){
			if(r[i-1]+x<l[i]){
//				cout<<"asd\n";
				return 0;
			}else{
				r[i]=min(r[i],r[i-1]+x);
			}
		}else if(r[i]<l[i-1]){
			if(l[i-1]-x>r[i]){
//				cout<<"fuck\n";
				return 0;
			}else{
				l[i]=max(l[i],l[i-1]-x);
			}
		}else{ //xiang jiao
			l[i]=max(l[i],l[i-1]-x);
			r[i]=min(r[i],r[i-1]+x);
		}
	}
	return 1;
}
signed main(){

	freopen("book.in","r",stdin);
	freopen("book.out","w",stdout);

	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	cin>>n>>x;
	for(int i=1;i<=n;i++){
		cin>>a[i].a>>a[i].b;
		h=min(h,a[i].a+a[i].b);
		sum+=a[i].a+a[i].b;
	}
	int l=0,r=h,mid,ans=0;
//	cout<<"r:"<<r<<"\n";
	while(l<=r){
		mid=(l+r)>>1;
		if(check(mid)){
//			cout<<"Yes\n";
			l=mid+1;
			ans=mid;
		}else{
//			cout<<"No\n";
			r=mid-1;
		}
	}
	cout<<sum-n*ans;
	
	return 0;
}
/*
h max
2 1
1000 1
1 1000

r: 2 1
l: 1 0

*/

提供 $O(n)$ 做法。

先把 $u_i$ 通过人类智慧用最小代价进行调整至 $|a_i-a_{i+1}| \le x$，再一起用 $\min u_i + d_i$ 推平即可。

时间复杂度绝对绝对绝对 $O(5n)$ $O(n)$，优于优先队列与二分。

还有谁

const int N=2e5+5;
int u[N],d[N];
int n,x,mnu=1;
void solve(){
	cin>>n>>x;
	for(int i=1;i<=n;i++) cin>>u[i]>>d[i];
	for(int i=1;i<=n;i++)
		if(u[i]<u[mnu]) mnu=i;
	int res=0;
	for(int i=mnu-1;i>=1;i--)
		if(u[i]-u[i+1]>x) res+=u[i]-u[i+1]-x,u[i]=u[i+1]+x;
	for(int i=mnu+1;i<=n;i++)
		if(u[i]-u[i-1]>x) res+=u[i]-u[i-1]-x,u[i]=u[i-1]+x;	
	int fin_l=2e9;	
	for(int i=1;i<=n;i++) fin_l=min(fin_l,u[i]+d[i]);
	for(int i=1;i<=n;i++) res+=u[i]+d[i]-fin_l;
	cout<<res<<'\n';	
}