题解

思路分析

这是一道 贪心 + 单调栈 + 前缀和 的序列划分问题。

问题建模

• 将 $n$ 个城市的旅行序列划分成 $m$ 个月
• 每个月计算快乐值与疲劳值的差的绝对值 $d_i$
• 目标：最小化 $\max(d_1, d_2, \ldots, d_m)$，且字典序最小

核心思路

1. 前缀和转化

设 $b[i] = \sum_{j=1}^{i} (2 \cdot \text{has\_景点}[j] - 1)$，即：

• 有景点 $+1$
• 无景点 $-1$

则第 $k$ 个月（从 $l$ 到 $r$）的差异值为：

2. 二分答案 + 贪心验证

二分最大差异值 $ans$，判断能否划分。

对于固定的 $ans$，贪心策略：

• 尽量延后划分（让每个月包含更多城市）
• 保证每个月的差异值 $\leq ans$

3. 单调栈维护候选点

对于每个位置 $i$（当前月末位置），维护一个单调栈存储候选的下一个月末点。

栈中维护：满足差异值 $\leq ans$ 的城市中，编号最小的。

4. 字典序最小

在满足差异值要求的前提下，每次选择编号最小的城市作为当月末点。

算法步骤

1. 预处理前缀和：

   • 计算 $b[i]$（有景点 $+1$，无景点 $-1$ 的前缀和）

2. 二分答案：

   • 二分最大差异值 $ans$

3. 贪心验证 + 字典序：

   • 对于每个月，找到满足条件的最小城市编号
   • 使用单调栈维护候选点
   • 判断能否划分成 $m$ 个月

4. 输出方案

复杂度分析

• 二分：$O(\log n)$
• 单调栈：$O(n)$
• 总时间复杂度：$O(n \log n)$
• 空间复杂度：$O(n)$

#include <bits/stdc++.h>
using namespace std;
int n,m,a[500005],b[500005],head[500005],tail[500005],pos[500005],l,r;
vector<int> v[500005],stk[500005];
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i]>>b[i],pos[a[i]]=i,b[i]+=1-3*b[i]+b[i-1],l=min(l,b[i]),r=max(r,b[i]);
	for(int i=0;i<=r-l;i++) v[i].push_back(0),head[i]=1;
	for(int i=1;i<=n;i++) v[b[i]-l].push_back(i);
	for(int i=0;i<=r-l;i++) stk[i].resize(v[i].size());
	if(!b[n]&&v[-l].size()>m){
		for(int i=1,j=1;i<m;i++){
			for(;j<v[-l].size()-m+i;j++){
				while(head[-l]<=tail[-l]&&stk[-l][tail[-l]]>a[v[-l][j]]) tail[-l]--;
				stk[-l][++tail[-l]]=a[v[-l][j]];
			}
			cout<<stk[-l][head[-l]]<<' ',head[-l]++;
		}
		cout<<a[n]<<'\n';
		return 0;
	} 
	int ans=(abs(b[n])-1)/m+1;
	for(int i=1,j=1,lst=0;i<m;i++){
		for(;j<=n-m+i;j++){
			int x=b[j]-l;
			while(head[x]<=tail[x]&&stk[x][tail[x]]>a[j]) tail[x]--;
			stk[x][++tail[x]]=a[j];
		}
		int L=max(l,b[lst]-ans),R=min(r,b[lst]+ans),res=n+1;
		for(int j=L;j<=R;j++)
			if(abs(b[n]-j)<=ans*(m-i)){
				while(head[j-l]<=tail[j-l]&&pos[stk[j-l][head[j-l]]]<=lst) head[j-l]++;
				if(head[j-l]<=tail[j-l]) res=min(res,stk[j-l][head[j-l]]);
			}
		cout<<res<<' ',lst=pos[res];
	}
	cout<<a[n]<<'\n'; 
	return 0;
}

题解

设原序列中第 $i$ 个城市的“快乐值–疲劳值”贡献分别为 $+1/-1$，对其做前缀和即可把任意一段的净快乐值写成 b[r] - b[l-1]，其中 $b[i]$ 表示前 $i$ 个城市的净差。我们要把整条路线划成 $m$ 段，使得每段的净差绝对值的最大值最小，再在最优值下取字典序最小的分割点。

首先观察答案的下界：整段旅行的净差为 |b[n]|，即使用 $m$ 段至少也要有一段的绝对值不小于 $\lceil |b[n]| / m \rceil$。证明可知这个下界总是可行的，因此直接把它当成目标上限 $ans$。
随后，把所有 $b[i]$ 的取值离散化到区间 $[l, r]$，按照差值把下标分桶，并为每个桶维护一个单调队列（队列中按出现顺序存放当前还未“过期”的城市编号并保持编号递增）。我们沿着原路线扫描，当指针 $j$ 向前移动时，就把城市 $j$ 放入对应桶的队列中——这意味着我们允许本月在城市 $j$ 结束。

在选择第 $i$ 个月的休息城市时，既要保证本段的净差不超过 $ans$，也要保证剩余月份仍有希望完成旅程。前一个条件对应 $|b[j] - b[lst]| \le ans$；后一个条件可以转化成当前结束时的前缀差 $b[j]$ 与终点的差 $b[n]$ 在剩余月份内仍有可能被摊平，即 $|b[n] - b[j]| \le ans \times (m - i)$。满足条件的候选在对应桶的队列里取（由于队列维护的是递增的城市编号且及时弹出已经被划分到前面月份的“过期城市”，我们总能拿到字典序最小的方案）。

依次确定 $m-1$ 个分割点，最后一个月必然停在 $a_n$。该做法始终在线性时间内扫描序列及桶，总复杂度 $O(n \log n)$（由离散化带来的排序开销）即可解决问题。

#include <bits/stdc++.h>
using namespace std;
int n,m,a[500005],b[500005],head[500005],tail[500005],pos[500005],l,r;
vector<int> v[500005],stk[500005];
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i]>>b[i],pos[a[i]]=i,b[i]+=1-3*b[i]+b[i-1],l=min(l,b[i]),r=max(r,b[i]);
	for(int i=0;i<=r-l;i++) v[i].push_back(0),head[i]=1;
	for(int i=1;i<=n;i++) v[b[i]-l].push_back(i);
	for(int i=0;i<=r-l;i++) stk[i].resize(v[i].size());
	if(!b[n]&&v[-l].size()>m){
		for(int i=1,j=1;i<m;i++){
			for(;j<v[-l].size()-m+i;j++){
				while(head[-l]<=tail[-l]&&stk[-l][tail[-l]]>a[v[-l][j]]) tail[-l]--;
				stk[-l][++tail[-l]]=a[v[-l][j]];
			}
			cout<<stk[-l][head[-l]]<<' ',head[-l]++;
		}
		cout<<a[n]<<'\n';
		return 0;
	} 
	int ans=(abs(b[n])-1)/m+1;
	for(int i=1,j=1,lst=0;i<m;i++){
		for(;j<=n-m+i;j++){
			int x=b[j]-l;
			while(head[x]<=tail[x]&&stk[x][tail[x]]>a[j]) tail[x]--;
			stk[x][++tail[x]]=a[j];
		}
		int L=max(l,b[lst]-ans),R=min(r,b[lst]+ans),res=n+1;
		for(int j=L;j<=R;j++)
			if(abs(b[n]-j)<=ans*(m-i)){
				while(head[j-l]<=tail[j-l]&&pos[stk[j-l][head[j-l]]]<=lst) head[j-l]++;
				if(head[j-l]<=tail[j-l]) res=min(res,stk[j-l][head[j-l]]);
			}
		cout<<res<<' ',lst=pos[res];
	}
	cout<<a[n]<<'\n'; 
	return 0;
}