分析
求的是最大值最小，肯定容易想到二分，该题目的答案的单调性是存在的，因为如果你找到一组合法的解，可以将距离最大的两个区间的距离再增大，这样更大的答案一定是能得到的。
既然我们已经得到了二分的合理性，那么我们需要考虑的只有如何检验一个答案的合理性。如果我们往序列中加入一个新区间，此时会影响与其相交的区间可以放置的位置范围，但是这样很难找到一个区间应该放在它对应的位置范围中的哪一个位置。既然如此，我们不如直接将每次加入的区间放在序列末尾，这样就省去了寻找一个区间可以放置在序列中的位置的范围，只需要知道区间可以放置的位置的最大值即可。
我们再考虑统计一个 \(cnt_{i,j}\) 表示在加入第 \(i\) 个区间时，必须要放置在 \([i,j]\) 的区间有多少个，显然 \(cnt_{i,j}\le j-i+1\)，不然区间数大于位置个数，无解。有解的情况，找到第一个 \(cnt_{i,j}=j-i+1\) 的位置，这 \(j-i+1\) 个区间会刚好将位置 \([i,j]\) 放满。在这 \(j-i+1\) 个区间中，显然影响其它区间数量最少的区间放在最前面是最优的。假定我们选择区间 \(x\) 作为我们放在 \(i\) 位置的的区间，存在一个区间 \(y\) 满足必须放在位置范围 \([i,j]\) 内且 \(r_y>r_x\)，如果此时有一个另外的区间 \(z\)，满足 \(r_z>l_x,r_z>l_y\)，那么显然 \(x\) 和 \(z\) 相较于 \(y\) 和 \(z\) 来说更不容易相交。如果区间 \(z\) 仅和区间 \(x\) 相交不和区间 \(y\) 相交，那么 \(z\) 一定在 \(x\) 之前被放置。因此我们在选择放在 \(i\) 位置的区间可以直接选择必序放在位置范围 \([i,j]\) 内的区间中 \(r\) 最小的。
Code
点击查看代码
#include<bits/stdc++.h>
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=f==1?x:-x;
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2010;
int n,l[N],r[N],ans_pos[N],pos_max[N],flag[N],cnt[N],Ans[N];
bool check(int dis){
for(int i=1;i<=n;i++){
flag[i]=0;//flag表示区间i的位置是否已经选定
pos_max[i]=n;//pos_max表示区间i在排列中位置的最大值
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cnt[j]=0;
}
for(int j=1;j<=n;j++){
if(!flag[j]){
cnt[pos_max[j]]++;
}
}
for(int j=1;j<=n;j++){
cnt[j]+=cnt[j-1];
}//前缀和统计cnt
for(int j=i;j<=n;j++){
if(cnt[j]>j-i+1){//不合条件的情况
return 0;
}
}
int mx=0;
for(int j=i;j<=n;j++){
if(cnt[j]==(j-i+1)){
mx=j;
break;
}
}
int pos=n+1;
for(int j=1;j<=n;j++){
if(!flag[j]&&pos_max[j]<=mx&&r[j]<r[pos]){
pos=j;
}//寻找最优区间
}
flag[pos]=1;
ans_pos[i]=pos;//标记若最大值为dis,排列中第i位的区间为哪个
for(int j=1;j<=n;j++){
if(l[j]<=r[pos]&&l[pos]<=r[j]){
pos_max[j]=min(pos_max[j],i+dis);
}//更新限制
}
}
return 1;
}
signed main(){
read(n);
r[n+1]=INT_MAX;
for(int i=1;i<=n;i++){
read(l[i]),read(r[i]);
}
int left=1,right=n-1;
while(left<=right){
int mid=(left+right)>>1;
if(check(mid)){
right=mid-1;
memcpy(Ans,ans_pos,sizeof(ans_pos));//找到答案并更新
}
else{
left=mid+1;
}
}
for(int i=1;i<=n;i++){
write_space(Ans[i]);
}
return 0;
}