专栏文章

P14385 [JOISC 2017] 门票安排 / Arranging Tickets 题解

lliuziqin
P14385题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mind3e6b
此快照首次捕获于
2025/12/02 00:26
3 个月前
此快照最后确认于
2025/12/02 00:26
3 个月前
查看原文
神仙性质题，不愧是 JOISC。
显然，我们可以将题目转化为给定 ∑ci\sum c_i 条线段，可以将若干条线段取其补集，求 max⁡ai\max a_i 的最小值。
我们定义对一个线段进行翻转表示取该线段的补集。

subtask 1,2

性质1：答案满足单调性。
这说明我们可以用二分答案解决问题。
性质2：对于一个翻转线段的集合 SS，其中所有线段的交集一定不为空。
证明：考虑反证法，假设存在两条线段 [l1,r1],[l2,r2][l_1,r_1],[l_2,r_2] 满足 r1<l2r_1 < l_2，将其翻转后对于 i∈[l1,r1],[l2,r2]i \in [l_1,r_1],[l_2,r_2] 的 aia_i 不变，其余的加 2，显然一定不优。
也就是说我们可以尝试找出一个 tt 满足翻转区间集 SS 的交集包含 tt。
考虑二分一个 TT，接下来考虑如何 check。
我们假设 pip_i 表示所有线段均不翻转时的 aia_i，qiq_i 表示翻转线段集合 SS 后的 aia_i，ziz_i 表示只统计 SS 中线段的 aia_i，此时则有 qi=pi−2zi+ztq_i=p_i-2z_i+z_t，显然
2zi≥pi−T+zt2z_i \ge p_i-T+z_t
所以说如果说我们能确定 tt 和 ztz_t，就能确定 ziz_i 的下线和枚举集合 SS 的大小。
接下来我们就把问题转化为了给定 tt 和 ztz_t，判断是否满足
⌈pi+zt−T2⌉≤zi≤zt\lceil \frac{p_i+z_t-T}{2}\rceil\le z_i \le z_t
考虑枚举 i∈[1,p]i \in[1,p]，依次将 l≤il \le i 且 r≥ir\ge i 的加入堆，再贪心选择 rr 最大的线段加入直到满足条件，如果做不到就不合法。
注意，此时的 zt≥max⁡pi−Tz_t \ge\max p_i-T，不然 qt>Tq_t >T，ztz_t 并不合法。
这一部分的代码如下：
C
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
const int INF=1e15;
struct node{
	int l,r,v;
}a[N];
bool operator <(node a,node b){
	return a.r<b.r;
}
vector<node>v[N];
int n,m;
int p[N],z[N];
bool chk(int t,int zt,int T){
	for(int i=t+1;i<=n;i++)z[i]=0;
	priority_queue<node>q;
	int sum=0;
	for(int i=1;i<=t;i++){
		int lim=(p[i]+zt-T+1)/2;
		for(node j:v[i])if(j.r>t)q.push(j);
		while(sum<lim&&!q.empty()){
			node u=q.top();
			q.pop();
			int date=min(lim-sum,u.v);
			sum+=date;
			z[u.r]-=date;
			u.v-=date;
			if(u.v)q.push(u);
		}
		if(sum<lim)return 0;
	}
	z[t]=sum;
	for(int i=t+1;i<=n;i++){
		z[i]+=z[i-1];
		if(z[i]*2<p[i]+zt-T)return 0;
	}
	return 1;
}
bool check(int mid){
	int mx=0;
	for(int i=1;i<=n;i++)mx=max(mx,p[i]-mid);
	for(int t=1;t<=n;t++)
	for(int zt=mx;zt<=p[t];zt++){
		if(chk(t,zt,mid)){
			return 1;
		}
	}
	return 0;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i].l>>a[i].r>>a[i].v;
		if(a[i].l>a[i].r)swap(a[i].l,a[i].r);
		v[a[i].l].push_back(a[i]);
		p[a[i].l]+=a[i].v;
		p[a[i].r]-=a[i].v;
	}
	for(int i=1;i<=n;i++)p[i]+=p[i-1];
	int l=0,r=INF,ans=0;
	while(l<r){
		int mid=(l+r)>>1;
		if(check(mid))r=mid,ans=mid;
		else l=mid+1;
	}
	cout<<ans<<"\n";
}

subtask 3

显然，目前的瓶颈在于暴力枚举 tt 和 ztz_t，考虑挖掘更多性质进行优化。
性质3：对于目前 SS 所有线段的并 [L,R][L,R]，最优方案一定满足 max⁡i∈[L,R]qi≥max⁡qi−1\max_{ i\in[L,R]}q_i \ge \max q_i-1。
证明：考虑反证法，我们假设存在一种方案满足 max⁡i∈[L,R]qi≤max⁡qi−2\max_{i \in[L,R]}q_i \le \max q_i-2。
首先这种方案中 SS 一定不包含线段 [L,R][L,R]，继续考虑反证法。
我们假设存在一个线段 I=[L,R]I=[L,R]，考虑翻转该线段。
  • i∈[L,R],qi′=qi+1i \in [L,R],q'_i=q_i+1
  • i∉[L,R],qi′=qi−1i\notin [L,R],q'_i=q_i-1
由 max⁡i∈[L,R]qi≤max⁡qi\max_{i \in [L,R]}q_i \le \max q_i 可得出 arg max⁡qi∉[L,R]\argmax q_i \notin [L,R]，显然翻转 II 更优。
现在我们来考虑以下调整方案：
  1. 如果 ∣S∣≤2|S| \le 2 或 max⁡i∈[L,R]qi≥max⁡qi−1\max_{i\in [L,R]}q_i \ge \max q_i-1，停止操作。
  2. 我们选择一个左端点为 LL 和一个右端点为 RR 的两个区间，将它们移除 SS，此时对于 i∈[L,R]i \in [L,R] 的 qiq_i 不变，对于 i∉[L,R]i \notin [L,R] 变为 qi−2q_i-2，接着回到操作 1。
显然，进行调整后的 max⁡i∈[L,R]qi≤max⁡qi−1\max_{i \in [L,R]} q_i \le \max q_i-1，得证。
于是我们只需判断 zt=pt−Tz_t=p_t-T 和 zt=pt−T+1z_t=p_t-T+1 两种情况即可。
这一部分的 check 如下：
C
bool check(int mid){
	int mx=-INF;
	for(int i=1;i<=n;i++)mx=max(mx,p[i]-mid);
	for(int i=1;i<=n;i++){
		bool ans=0;
		if(p[i]-mid>=mx)ans|=chk(i,p[i]-mid,mid);
		if(p[i]-mid+1>=mx)ans|=chk(i,p[i]-mid+1,mid);
		if(ans)return 1;
	}
	return 0;
}

subtask 4,5

此时我们的复杂度瓶颈来到了枚举 tt 上面。
性质 4：设 t=arg max⁡i∈[L,R]t=\argmax_{i \in[L,R]}，如果说最优方案满足 qt≥maxqi−1q_t \ge max q_i-1，此时 SS 同时满足 pt=maxpip_t=maxp_i
证明：还是考虑反证法，我们假设存在最优方案 SS 满足 qt≥max⁡qi−1q_t\ge \max q_i-1 且 pt<max⁡pip_t <\max p_i，设 x=arg max⁡qix=\argmax q_i。
显然 x∉[L,R]x \notin [L,R]，因此，至少有一个线段没有包含 xx 即 zt>zxz_t >z_x，于是我们可以得出
px≥pt+1,zx≤zt−1p_x \ge p_t+1,z_x\le z_t-1
再联立之前的式子 qt=pt−zt,qx=px−2zx+ztq_t=p_t-z_t,q_x=p_x-2z_x+z_t 可以得出不等式
qx+2zx−zt≥qt+zt+1qx−qt≥2(zt−zx)+1∵zx≤zt−1∴2(zt−zx)≥2qx≥qt+3q_x+2z_x-z_t\ge q_t+z_t+1 \\q_x-q_t \ge 2(z_t-z_x)+1 \\\because z_x\le z_t-1 \\\therefore 2(z_t-z_x) \ge 2 \\q_x \ge q_t+3
与原假设不符，得证。
于是我们将 tt 的范围缩小到了 pt=max⁡pip_t=\max p_i 的范围内。
性质 5：若一种方案满足 qt≥max⁡qi−1q_t \ge \max q_i-1，那么 {x∣px=max⁡pi}⊆[L,R]\{x|p_x =\max p_i\}\subseteq[L,R]。
证明：类似性质 4 的反证，我们设 ∃x∉[L,R],px=max⁡pi\exists x \notin[L,R],p_x=\max p_i，显然 px=pt,zx≤zt−1p_x=p_t,z_x \le z_t-1，于是我们就能得到以下不等式：
qx−qt=2(zt−zx)qx≥tt+2q_x-q_t=2(z_t-z_x) \\q_x \ge t_t+2
与原假设不符，得证。
于是我们将时间复杂度优化到了 O((n+m)log⁡n)O((n+m)\log n)，足以通过本题。
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
const int INF=1e15;
struct node{
	int l,r,v;
}a[N];
bool operator <(node a,node b){
	return a.r<b.r;
}
vector<node>v[N];
int n,m;
int p[N],z[N];
bool chk(int t,int zt,int T){
//	cout<<"sb\n";
	for(int i=t+1;i<=n;i++)z[i]=0;
	priority_queue<node>q;
	int sum=0;
	for(int i=1;i<=t;i++){
		int lim=(p[i]+zt-T+1)/2;
		for(node j:v[i])if(j.r>t)q.push(j);
		while(sum<lim&&!q.empty()){
			node u=q.top();
			q.pop();
			int date=min(lim-sum,u.v);
			sum+=date;
			z[u.r]-=date;
			u.v-=date;
			if(u.v)q.push(u);
		}
		if(sum<lim)return 0;
	}
	z[t]=sum;
	for(int i=t+1;i<=n;i++){
		z[i]+=z[i-1];
		if(z[i]*2<p[i]+zt-T)return 0;
	}
	return 1;
}
bool check(int mid){
	int mx=-INF;
	for(int i=1;i<=n;i++)mx=max(mx,p[i]-mid);
	for(int i=1;i<=n;i++){
		bool ans=0;
		if(p[i]-mid==mx){
			return chk(i,p[i]-mid,mid)|chk(i,p[i]-mid+1,mid);
		}
	}
	return 0;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i].l>>a[i].r>>a[i].v;
		if(a[i].l>a[i].r)swap(a[i].l,a[i].r);
		v[a[i].l].push_back(a[i]);
		p[a[i].l]+=a[i].v;
		p[a[i].r]-=a[i].v;
	}
	int res=0;
	for(int i=1;i<=n;i++)p[i]+=p[i-1],res=max(res,p[i]);
	int l=0,r=INF,ans=0;
	while(l<r){
		int mid=(l+r)>>1;
		if(check(mid))r=mid,ans=mid;
		else l=mid+1;
	}
	cout<<min(ans,res)<<"\n";
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...