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

liuziqin · 2025-11-06 10:53:16 · 题解

神仙性质题，不愧是 JOISC。

显然，我们可以将题目转化为给定 \sum c_i 条线段，可以将若干条线段取其补集，求 \max a_i 的最小值。

我们定义对一个线段进行翻转表示取该线段的补集。

subtask 1,2

性质1：答案满足单调性。

这说明我们可以用二分答案解决问题。

性质2：对于一个翻转线段的集合 S，其中所有线段的交集一定不为空。

证明：考虑反证法，假设存在两条线段 [l_1,r_1],[l_2,r_2] 满足 r_1 < l_2，将其翻转后对于 i \in [l_1,r_1],[l_2,r_2] 的 a_i 不变，其余的加 2，显然一定不优。

也就是说我们可以尝试找出一个 t 满足翻转区间集 S 的交集包含 t。

考虑二分一个 T，接下来考虑如何 check。

我们假设 p_i 表示所有线段均不翻转时的 a_i，q_i 表示翻转线段集合 S 后的 a_i，z_i 表示只统计 S 中线段的 a_i，此时则有 q_i=p_i-2z_i+z_t，显然

2z_i \ge p_i-T+z_t

所以说如果说我们能确定 t 和 z_t，就能确定 z_i 的下线和枚举集合 S 的大小。

接下来我们就把问题转化为了给定 t 和 z_t，判断是否满足

\lceil \frac{p_i+z_t-T}{2}\rceil\le z_i \le z_t

考虑枚举 i \in[1,p]，依次将 l \le i 且 r\ge i 的加入堆，再贪心选择 r 最大的线段加入直到满足条件，如果做不到就不合法。

注意，此时的 z_t \ge\max p_i-T，不然 q_t >T，z_t 并不合法。

这一部分的代码如下：

#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

显然，目前的瓶颈在于暴力枚举 t 和 z_t，考虑挖掘更多性质进行优化。

性质3：对于目前 S 所有线段的并 [L,R]，最优方案一定满足 \max_{ i\in[L,R]}q_i \ge \max q_i-1。

证明：考虑反证法，我们假设存在一种方案满足 \max_{i \in[L,R]}q_i \le \max q_i-2。

首先这种方案中 S 一定不包含线段 [L,R]，继续考虑反证法。

我们假设存在一个线段 I=[L,R]，考虑翻转该线段。

i \in [L,R],q'_i=q_i+1

i\notin [L,R],q'_i=q_i-1

由 \max_{i \in [L,R]}q_i \le \max q_i 可得出 \argmax q_i \notin [L,R]，显然翻转 I 更优。

现在我们来考虑以下调整方案：

如果 |S| \le 2 或 \max_{i\in [L,R]}q_i \ge \max q_i-1，停止操作。

我们选择一个左端点为 L 和一个右端点为 R 的两个区间，将它们移除 S，此时对于 i \in [L,R] 的 q_i 不变，对于 i \notin [L,R] 变为 q_i-2，接着回到操作 1。

显然，进行调整后的 \max_{i \in [L,R]} q_i \le \max q_i-1，得证。

于是我们只需判断 z_t=p_t-T 和 z_t=p_t-T+1 两种情况即可。

这一部分的 check 如下：

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

此时我们的复杂度瓶颈来到了枚举 t 上面。

性质 4：设 t=\argmax_{i \in[L,R]}，如果说最优方案满足 q_t \ge max q_i-1，此时 S 同时满足 p_t=maxp_i

证明：还是考虑反证法，我们假设存在最优方案 S 满足 q_t\ge \max q_i-1 且 p_t <\max p_i，设 x=\argmax q_i。

显然 x \notin [L,R]，因此，至少有一个线段没有包含 x 即 z_t >z_x，于是我们可以得出
p_x \ge p_t+1,z_x\le z_t-1
再联立之前的式子 q_t=p_t-z_t,q_x=p_x-2z_x+z_t 可以得出不等式
q_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
与原假设不符，得证。

于是我们将 t 的范围缩小到了 p_t=\max p_i 的范围内。

性质 5：若一种方案满足 q_t \ge \max q_i-1，那么 \{x|p_x =\max p_i\}\subseteq[L,R]。

证明：类似性质 4 的反证，我们设 \exists x \notin[L,R],p_x=\max p_i，显然 p_x=p_t,z_x \le z_t-1，于是我们就能得到以下不等式：
q_x-q_t=2(z_t-z_x) \\q_x \ge t_t+2
与原假设不符，得证。

于是我们将时间复杂度优化到了 O((n+m)\log n)，足以通过本题。

#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";
}