题解：AT_agc040_d [AGC040D] Balance Beam

· · 题解

题目传送门

AtCoder

AC 记录

把题目画到数轴上，左端是 0，右端是 n。

考虑什么时候是能追上。首先一定存在一个分界点 S，坐标为 s，此时答案为 \dfrac{s}{n}，当 Ringo 选的是其左边的点的时候都能追上，选到右边都追不上。S 肯定在某一段（j）内。

接下来考虑怎么判断能追上，由于每条线段里两人速度一致，那么如果能追上，一定存在一个端点（x），使得 Snuke 从 0 到达 x 用时比 Ringo 从 S 到达 x 用时少（或相等）。

记 Snuke 从 0 到达某个位置 p，用时 A(p)。Ringo 从 0 到达某个位置 p，用时 B(p)。用一下差分的思想，可以想到能追上的条件是存在 x 使得 A(x)\le B(x)-B(S)。

现在假设我们选好了 j 段以前的所有边，这些边的集合为 F。

考虑 j 后面的边，将其分为两类边，第一类 a_i<b_i，第二类 a_i\ge b_i。

显然，当走第一类边时，如果 Snuke 在后面，两人距离缩短。走第二类边时则增加。

贪心的想，我们应该尽量将第一类边放在前面，使得 Snuke 尽可能的追赶，否则一定不优。

继续思考。此时在第一类边与第二类边的分界处，Snuke 最可能追上 Ringo。所以如果最终能追上，x 就可以取这个分界处。

为了方便表示，设 S 到 j 的左端的距离为 f，到右端则为 1-f，第一类边的集合为 P，第二类边的集合为 Q。

可以发现 s=|F|+f，所以答案是 \dfrac{|F|+f}{n}，考虑根据前面的约束得到某种关系，再贪心的得到最大答案。

现在我们固定了 x，来拆开 A(x)\le B(x)-B(S)。

首先移项，变成 B(x)-A(x)\ge B(S)。

接下来展开 B(x),A(x),B(S)。

\sum\limits_{i\in F} b_i-a_i+b_j-a_j+\sum\limits_{i\in P} b_i-a_i\ge \sum\limits_{i\in F} b_i+f\times b_j

单独考虑左边：

\sum\limits_{i=1}^{n} b_i-a_i-\sum\limits_{i\in Q} b_i-a_i

注意到 b_i-a_i=\max(b_i-a_i,0)-\max(a_i-b_i,0)，同时 Q 中 a_i\ge b_i，所以 \forall i\in Q 有 \max(b_i-a_i,0)=0。那么可以化成下式。

\sum\limits_{i=1}^{n} \max(b_i-a_i,0)-\sum\limits_{i=1}^{n} \max(a_i-b_i,0)+\sum\limits_{i\in Q} \max(a_i-b_i,0)

回到原式，移项。

\sum\limits_{i=1}^{n} \max(b_i-a_i,0) \ge \sum\limits_{i=1}^{n} \max(a_i-b_i,0)-\sum\limits_{i\in Q} \max(a_i-b_i,0)+ \sum\limits_{i\in F} b_i+f\times b_j

合并右边：

\sum\limits_{i=1}^{n} \max(b_i-a_i,0) \ge \sum\limits_{i\in F} \max(a_i-b_i,0)+b_i+f\times b_j +\sum\limits_{i\in P} \max(a_i-b_i,0)+\max(a_j-b_j,0)

由于 \forall i\in P 有 b_i>a_i，所以 \sum\limits_{i\in P} \max(a_i-b_i,0)=0。

同时 \max(a_i-b_i,0)+b_i=\max(a_i,b_i)。

得到：

\sum\limits_{i=1}^{n} \max(b_i-a_i,0) \ge \sum\limits_{i\in F} \max(a_i,b_i)+f\times b_j +\max(a_j-b_j,0)

继续移项：

\sum\limits_{i=1}^{n} \max(b_i-a_i,0) -\sum\limits_{i\in F} \max(a_i,b_i) -\max(a_j-b_j,0)\ge f\times b_j

把 b_j 移到左边：

\dfrac{\sum\limits_{i=1}^{n} \max(b_i-a_i,0) -\sum\limits_{i\in F} \max(a_i,b_i) -\max(a_j-b_j,0)}{b_j}\ge f

所以我们得到了 f 的最大值。

考虑如何分配 |F| 和 f 使得答案最大化。

显然 |F| 一次可以增加 1，而 f<1，所以优先增大 |F|。

为了取尽可能多的线段放进 F，\sum\limits_{i\in F} \max(a_i,b_i) 应在 |F| 不变的情况下尽量小，所以将原数组按 \max(a_i,b_i) 从小到大排序，贪心的选择前缀。

显然可以求出 \sum\limits_{i=1}^{n} \max(b_i-a_i,0) -\sum\limits_{i\in F} \max(a_i,b_i)\ge 0 时最大的 |F|。

随后枚举 j，分类讨论：

  1. 如果 j 在原本选择的 F 中，从 F 中去掉 j，再选择其它线段中 \max(a_i,b_i) 最小的线段加入 F。
  2. 否则直接计算。

随后便可以计算 f，最后取最大答案输出即可。

AC Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
int n,pre[100005],sum,d[100005];
pair<int,int> p[100005];
signed main(){
    // freopen("big.in","r",stdin);
    // freopen("big.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>p[i].F>>p[i].S,sum+=max(p[i].S-p[i].F,0ll);
    sort(p+1,p+n+1,[](pair<int,int> a,pair<int,int> b){return max(a.F,a.S)<max(b.F,b.S);});//按照max(a[i],b[i])排序
    for(int i=1;i<=n;i++){
        pre[i]=pre[i-1]+max(p[i].F,p[i].S);
        d[i]=max(p[i].F-p[i].S,0ll);
    }
    int pos=upper_bound(pre+1,pre+1+n,sum)-pre-1;//计算最大的|F|
    int ans1=0,ans2=1;
    for(int i=1;i<=n;i++){
        int summ=sum-d[i];
        if(i<=pos) summ=summ-pre[pos+1]+max(p[i].F,p[i].S);
        else summ=summ-pre[pos];
        if(summ>p[i].S) summ=p[i].S;
        if(summ>0){
            if((__int128)ans1*p[i].S<(__int128)ans2*summ){//取最大的f
                ans1=summ;
                ans2=p[i].S;
            }
        }
    }
    ans1+=pos*ans2;//加|F|
    ans2*=n;//分母原本为n
    int gcd=__gcd(ans1,ans2);//约分
    cout<<ans1/gcd<<' '<<ans2/gcd;
    return 0;
}