P10046

cryozwq · 2024-01-24 22:48:41 · 题解

一种比较神秘的做法，洛谷通过后本地把小数据都对拍了下，应该保真。

考虑到 |a-b|=\max (a-b,b-a)，则原问题事实上等价于给每个 a_i,b_i 标号，满足对于所求路径上一条边 i \to j，a_i,b_j 不同号。（到这里比较正常）

如果不考虑整体要连成一个大环，限制等价于给 a_i 标的负号的数量等于给 b_i 标的正号的数量，那么这个问题是容易的，枚举分界线即可，设分界线为 k （排序后的 a_1 到 a_k 为负，对应的 b_{n-k+1} 到 b_n 为正）。这么做的问题是什么？我们得到的答案事实上是若干个环构成的，而不是一个，所以会使得算出来的更大。

考虑在得到这样一个方案后调整，对于两个环上两条边 i\to j 和 i' \to j' 调整为 i \to j'，i' \to j 就合并了两个环。

接下来阐述两个个较为简单的结论（由于证明比较显然，故不赘述，有问题私信），称 a_i < b_j 的边 i \to j 为正边，否则为负边。边 i\to j 在数轴上代表的线段为 [\min(a_i,b_j),\max(a_i,b_j) ]。

• 对于任意两条边 i \to j 与 i' \to j'，若两者在数轴上代表的线段无交集，调整为 i \to j' 与 i' \to j 一定更优 。

• 对于任意两条边 i \to j 与 i' \to j'，若两者在数轴上代表的线段有交集，则两条边正负不同时，调整为 i \to j' 与 i' \to j 会使答案减小，否则对答案无影响，下图列了两个例子，其余情况类似（黑色未调整，蓝色调整后）：

由于此时已经为理论最优解，故无法再找到两条边所代表线段无交集，则合并两个环时，若两个环都有正边或者负边，则合并不减小答案，我们现在要尽可能减小合并带来的损失，则若存在一个既有正边又有负边的环，那么合并为一个环一定无损失，先判掉。

否则一个环一定要么都是负边，要么都是正边，这些环内部合并不产生损失，因此需要且仅需要一次有损失的合并就能保证所有环最后合并为一个，接下来，我们只需要最小化这次合并的损失。那么我们形式化描述一下这个损失的具体大小，其实就是选的两条边代表线段的交的大小的 2 倍，为了使其尽量小，简单贪心可知即为分界点 k 对应的 k \to n-k+1 和 k+1 \to n-k 这两条边所产生的交一定是所有正负不同的边对应线段交最小的。

唯一的问题是，只合并这两条边一定在所有情况下都能保证所有环合并完吗？并不是。需要进行分类讨论：

• 如果两条线段并非包含关系，画图可知这两条边调整后一定还是为正边和负边，则一定合法。

• 如果属于包含关系，则调整后为两条正边或者两条负边，这里以两条正边举例，负边同理，这样的话，合并剩余的正环无需额外代价，但是对于负环就无法合并，所以我们需要在这次正负边合并前先把所有负环合并起来，只要这条需要合并的负边对应的环不是自环，我们就可以拿这个环上其他边去先合并完其余负环，再用这条边和刚刚说的那条正边合并达到最小损失。

也就是说，当且仅当这两条边对应线段属于包含关系且被包含者对应的环是一个自环，这种方案不成立，这种情况下，不得不用这条边去和其他负环的边合并导致对应线段变大，但是合并一次之后这个环就不是自环了，只需要让这次合并对这条边对应线段变化尽量小，简单讨论后贪心即可，不再赘述。

综上，通过这一系列较为繁杂的讨论，我们事实上得到了一个较为简洁的解法。

代码：

#include<bits/stdc++.h>
#define mp make_pair
#define fr first
#define sc second
using namespace std;
typedef long long ll;
int n;
const ll inf=1e17;
const int maxn=2e6+5;
ll a[maxn],b[maxn];
pair<ll,int>ta[maxn],tb[maxn];
ll sa[maxn],sb[maxn];
ll mul;
map<int,int>g;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i],&b[i]),ta[i]=mp(a[i],i),tb[i]=mp(b[i],i);
    sort(ta+1,ta+n+1);
    sort(tb+1,tb+n+1);
    for(int i=1;i<=n;i++)sa[i]=sa[i-1]+ta[i].fr;
    for(int i=1;i<=n;i++)sb[i]=sb[i-1]+tb[i].fr;
    ll ans=0;
    int k=0;
    for(int i=0;i<=n;i++){
        ll val=-sa[i]+(sa[n]-sa[i])-sb[n-i]+(sb[n]-sb[n-i]);
        ans=max(ans,val);
        if(ans==val)k=i;
    }
    for(int i=1;i<=k;i++){
        g[ta[i].sc]++;
        g[tb[n-i+1].sc]--;
    }
    bool fl=0;
    for(auto v:g)fl|=(v.sc>0);
    if(fl){
        cout<<ans;
        return 0;
    }
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    ll mul=inf;
    int a1=k,a2=k+1,b1=n-k+1,b2=n-k;
    if(k==0||k==n){
        cout<<ans<<endl;
        return 0;
    } 
    if(a[a1]<=b[b2]){
        if(a[a2]<=b[b1]){
            if(a2==n||ta[a2].sc!=tb[b2].sc)mul=2ll*(a[a2]-b[b2]);
            else{
                int b3=n-k-1,a3=a2+1;
                mul=min(2ll*(a[a2]-max(b[b3],a[a1])),2ll*(min(a[a3],b[b1])-b[b2]));
            }
        } 
        if(b[b1]<=a[a2])mul=2ll*(b[b1]-b[b2]);
    }
    else{
        if(a[a2]<=b[b1])mul=2ll*(a[a2]-a[a1]);
        if(b[b1]<=a[a2]){
            if(b1==n||tb[b1].sc!=ta[a1].sc)mul=2ll*(b[b1]-a[a1]);
            else{
                int b3=b1+1,a3=a1-1;
                mul=min(2ll*(b[b1]-max(a[a3],b[b2])),2ll*(min(b[b3],a[a2])-a[a1]));
            }
        }
    }
    cout<<ans-mul<<endl;
    return 0;
}