[題解]CF1666E Even Split
二分答案好題。
下文中，記 Segmentland 的長度為 \(s\)。
我們先不考慮輸出方案，僅考慮如何計算最小極差 \(d\)。
不難 \(d\) 具有單調(diào)性，可以二分求解。
對于每一個 \(d\)，我們可以枚舉區(qū)間長度的下界 \(l\)，再判定能否做到所有區(qū)間的長度都在 \([l,l+d]\) 內(nèi)。
我們發(fā)現(xiàn)這個 \(l\) 也是可以二分的，原因是我們可以 \(O(n)\) 判定當前 \(l\) 的值是偏大、偏小還是正好，可參照下面的代碼：
int check(int l,int r){//長度在[l,r]內(nèi)是否合法（-1為小了，0為正好，1為大了）
int x=0,y=0;//x,y存儲可能的右端點范圍
for(int i=1;i<=n;i++){
if(x+l>a[i+1]) return 1;
if(y+r<a[i]) return -1;
x=max(x+l,a[i]);
y=min(y+r,a[i+1]);
}
if(x>s) return 1;
if(y<s) return -1;
return 0;
}
這樣我們就能在 \(O(n\log n\log s)\) 的復(fù)雜度內(nèi)完成求解。
接下來考慮如何輸出方案。
令第 \(i\) 個分界點的位置為 \(d_i\)（有 \(d_0=0,d_n=s\)），長度區(qū)間為 \([mn,mx]\)。
則我們的構(gòu)造需要滿足的條件為：
- \(d_i\in[a_i,a_{i+1}]\)
- \(d_i-d_{i-1}\in [mn,mx]\)
前面的過程保證了一定存在合法的方案，所以我們盡可能緊貼著下界構(gòu)造。即：
- 先對于 \(i=1,2,\dots,n\)，令 \(d_i=\max(a_i,d_{i-1}+mn)\)。
- 再對于 \(i=n,\dots,2,1\)，令 \(d_{i-1}=\max(d_{i-1},d_i-mx)\)。
點擊查看代碼
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int s,n,a[N],mn,mx,d[N];
int check2(int l,int r){//長度在[l,r]內(nèi)是否合法（-1為小了）
int x=0,y=0;
mn=l,mx=r;
for(int i=1;i<=n;i++){
if(x+l>a[i+1]) return 1;
if(y+r<a[i]) return -1;
x=max(x+l,a[i]);
y=min(y+r,a[i+1]);
}
if(x>s) return 1;
if(y<s) return -1;
return 0;
}
bool check(int x){//x作為極差是否合法
int l=0,r=s;
while(l<=r){
int mid=(l+r)>>1,t=check2(mid,mid+x);
if(t==-1) l=mid+1;
else if(t==1) r=mid-1;
else return 1;
}
return 0;
}
void get_ans(int x){
check(x);
d[n]=s;
for(int i=1;i<n;i++) d[i]=max(d[i-1]+mn,a[i]);
for(int i=n;i;i--) d[i-1]=min(d[i-1],d[i]-mx);
for(int i=1;i<=n;i++) cout<<d[i-1]<<" "<<d[i]<<"\n";
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>s>>n;
for(int i=1;i<=n;i++) cin>>a[i];
a[n+1]=s;
int l=0,r=s;
while(l<r){
int mid=(l+r)>>1;
if(check(mid)){
r=mid;
}else{
l=mid+1;
}
}
get_ans(l);
return 0;
}
浙公網(wǎng)安備 33010602011771號