【2023NOI模拟赛36】A 做题记录

给定 $n$ 个区间 $[l_i,r_i]$，构造一个 $n$ 的排列 $p$，最小化 $\sum\limits_{i=1}^{n-1}\max(0,r_{p_i}-l_{p_{i+1}})-l_1$，输出方案。

$1\le n\le 5\times 10^5$。

考虑拆掉 $\max$，再讨论加回来新增的贡献。

拆掉 $\max$ 后，答案为 $\sum\limits_{i=1}^n r_i-\sum\limits_{i=1}^n l_i-r_n$。

那么为了让新增的贡献尽可能少，则我们要让 $\max(0,r_{p_i}-l_{p_{i+1}})$ 取 $0$ 的位置尽可能少，并且要让 $r_n$ 尽可能大。

若两个区间相交，那么在它们之间连一条边。考虑只有一个连通块的情况，显然可以把 $l$ 最小的和 $r$ 最大的两个区间以及它们之间的 “链”拉出来，然后把剩下的区间按照 $r$ 从大到小放到前面：

这样没有取 $0$ 的位置且 $r_n$ 最大，显然满足答案最小。

对于有多个连通块的情况，设从左到右第 $i$ 个连通块的左端点为 $lb_i$，右端点为 $rb_i$，那么显然新增的贡献至少是 $\sum lb_{i+1}-rb_i$，那么显然按照只有一个连通块的方法构造还是最优的。

时间复杂度 $O(n\log n)$（排序）。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <set>
#include <deque>

using namespace std;

typedef long long ll;

const int S=500005;

struct node
{
	int l,r,id;
}a[S];

int n,m;
deque<int> res;
set<int> st;
int ans[S];

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].r),a[i].id=i;
	sort(a+1,a+n+1,[&](auto x,auto y){return x.l<y.l;});
	for(int i=1,mxr=0;i<=n;i++)
	{
		if(a[i].r>mxr) res.push_back(a[i].id),st.insert(a[i].id);
		mxr=max(mxr,a[i].r);
	}
	sort(a+1,a+n+1,[&](auto x,auto y){return x.r<y.r;});
	for(int i=1;i<=n;i++) if(!st.count(a[i].id)) res.push_front(a[i].id);
	sort(a+1,a+n+1,[&](auto x,auto y){return x.id<y.id;});
	while(!res.empty()) ans[res.size()]=res.back(),res.pop_back();
	ll sum=0;
	for(int i=1;i<=n-1;i++) sum+=max(0,a[ans[i]].r-a[ans[i+1]].l);
	sum+=m-a[ans[1]].l;
	printf("%lld\n",sum);
	for(int i=1;i<=n;i++) printf("%d ",ans[i]);
	printf("\n");
	return 0;
}