浅谈二分答案

通常来说，当我们看到题设中的 “最大值最小化” 或 “最小值最大化”，就会想到二分答案。

这一层理解可以帮助我们识别题型，但跳跃了一层逻辑，为什么二分答案是可行的？到底什么类型的问题可以二分答案？判定函数是从哪来的？

二分查找与二分答案

二分查找是在有序序列或单调布尔序列中寻找边界；二分答案则先把候选答案 $x$ 转化为判定问题，再在答案域中寻找 check(x) 的真假分界。二者共享“利用单调性寻找边界”的工具，但本文主要讨论后者。

一、从求最优值到判断一个阈值

考虑一个最小值最大化问题：在所有方案中，让某个评价量尽量大。

如果直接求最优值的话，我们会同时面对两个问题：

1. 怎样构造一个方案；
2. 怎样证明它已经是最优的。

但是固定一个候选答案 $x$ 后，问题会变成：是否存在一个方案使评价量至少为 $x$？如果存在达到 $x$ 的方案，那么同一个方案也能满足所有 $x' \le x$；如果连 $x$ 都达不到，那么更大的阈值也不可能达到。

所以判定结果呈现为：可行　...　可行 ｜ 不可行　...　不可行，最优值就是最后一个可行位置。

如果寻找的是最小可行阈值，判定结果则通常呈现为：不可行　...　不可行 ｜ 可行　...　可行，此时找的是第一个可行位置。

Q0

P2440 木材加工
有 $n$ 根原木，要切出至少 $k$ 段长度相同的正整数木段，允许原木剩余，求木段长度的最大值。

数据规模：$1\le n\le 10^5$，$1\le k,L_i\le 10^8$。

固定所求的木段长度 $x$，第 $i$ 根原木能够切出 $\displaystyle \left\lfloor \frac{L_{i}}{x} \right\rfloor$ 段木材。所以只需要判断 $\displaystyle check(x) \iff \sum_{i=1}^{n} \left\lfloor \frac{L_{i}}{x} \right\rfloor \ge k$。

随着 $x$ 的增大，能够切出来的木段数量只会减少，所以要找最后一个可行的 $x$。

由此我们发现，“最大值最小化 / 最小值最大化”只是线索，更重要的是固定答案后能否高效判定，以及判定结果是否随着答案大小单调变化。

二分只减少需要尝试的阈值数量，并不会自动加速判定。若一次判定复杂度为 $T_{check}$，整数答案范围为 $[L,R]$，总复杂度通常是 $\mathcal O(T_{check}\log(R-L+1))$；实数二分固定迭代 $K$ 次时则是 $\mathcal O(KT_{check})$。

二、check函数如何构建

固定阈值是将原求解最值的问题转化为：对当前阈值是否合法的判断的问题。

连续段分段

对比下面两个相似的问题：

Q1

P1182 数列分段 Section II
把一个非负整数数列分成恰好 $M$ 个连续段，使所有段中最大的段和尽量小。

Q2

P3017 Brownie Slicing G
先把非负权值网格切成 $A$ 条水平带，再把每条水平带独立竖切成 $B$ 块，使所有 $A\times B$ 个矩形中的最小权值尽量大。

对于 Q1 来说，固定了最大的段和 $x$，问题转化为：能否完成划分，并保证每段和都不超过 $x$。为了让所需段数最少，每一段都应该尽可能向右延伸，只有加入下一个元素会超过 $x$ 时才切分。

贪心得到的是满足段和上界 $x$ 时最少需要的段数。如果最少段数不超过 $M$，还可以继续把已有连续段拆开。由于数列元素非负，拆分不会让任何一段的和增大，所以一定能够补成恰好 $M$ 段。

对于 Q2 来说，固定了每块的最小权值 $x$，问题转化为：能否切出足够多块，并保证每块权值都不小于 $x$。为了让能够形成的合法块数尽可能多，当前块一旦达到阈值，就应该立即切掉，把更多权值留给后面的块。

Q1 和 Q2 都是基于贪心的思想，而且都依赖于权值非负。而决定切分方向的是，当前阈值限制的是 上界(Q1) 还是 下界(Q2)。

• 上界约束下，为了减少段数，应当尽量晚切；
• 下界约束下，为了增加合法块数，应当尽量早切。

对于 Q2，固定一段连续行后，从左到右“当前列块一旦达到 $x$ 就立即切开”能够得到最多的合法列块。外层同理：一旦当前若干行已经能够切出 $B$ 个合法列块，就立即结束这一条水平带。由于权值非负，提前切割只会给后面的水平带留下更多行和权值，不会降低后续可行性。若存在某个可行划分，贪心得到的第一条水平带结束位置不会晚于该划分；删去第一条带后可以重复这一论证，所以最终切出的水平带数量是最大的。

▶

二分上下界

// Q1 寻找最小可行值
while( l <= r ) {
	ll mid = ( l + r ) >> 1;
	if( check( mid ) ) ans = mid, r = mid - 1;
	else l = mid + 1;
}
// Q2 寻找最大可行值
while( l <= r ) {
	int mid = ( l + r ) >> 1;
	if( check( mid ) ) ans = mid, l = mid + 1;
	else r = mid - 1;
}

坐标轴上的问题

这一类坐标轴上的距离问题通常表现为 “最大间距最小化” 和 “最小间距最大化”。但它跟上面连续段分段的区别，在于每一次操作可能会影响后面间距的结构。同样还是举两个题目为例：

Q3

P3853 路标设置
在一条公路上最多增加 $K$ 个整数位置路标，使相邻路标最大距离尽量小；起点和终点已有路标。

Q4

P2678 跳石头
在起点与终点之间至多移走 $M$ 块岩石，使相邻保留岩石之间的最短跳跃距离尽可能大。

对于 Q3 来说，固定最大允许间距 $x$，对于一个长度为 $d$ 的原始间距，要把它拆成若干个长度都不超过 $x$ 的段，至少需要增加 $\displaystyle \left\lceil \frac{d}{x} \right\rceil - 1 = \left\lfloor \frac{d-1}{x} \right\rfloor$ 个路标。

由于各个原始间距互不影响，所以可以直接把所有的新增路标数量相加，然后拿新增路标的总数和 $K$ 做判断。

对于 Q4 来说，固定最小允许距离 $x$，若当前岩石和上一个保留位置的距离小于 $x$，二者不能同时保留。此时删除当前岩石、保留更靠左的岩石，不会让后面的岩石更难满足距离限制；反而保留当前岩石，会缩短它和后续岩石之间的距离。

因此可以从左向右贪心：距离不足 $x$ 时删除当前岩石，否则保留当前岩石，并将它作为新的比较位置。

与 Q3 不同，删除一个岩石会把左右两个间隔合并，后续判断取决于此前保留了哪个位置，各个间隔之间不是独立的，所以没法分别计算然后求和。

Q5

CF2167E - khba Loves to Sleep!
一条线上有 $n$ 个朋友，需要在 $[0,x]$ 中选择 $k$ 个互异的整数位置放置传送门，使最早到达某个传送门的朋友所需时间尽可能长。

固定传送门到所有朋友的最小距离 $d$ 后，需要判断能否选择 $k$ 个位置，使每个传送门到每个朋友的距离都至少为 $d$。

对于朋友位置 $a_i$，所有满足 $|p-a_i|<d$ 的整数位置 $p$ 都不能放置传送门。于是每个朋友都会产生一个禁区，问题就转化为统计所有禁区补集中是否至少存在 $k$ 个整数点。

将朋友位置排序后，可用位置分别位于最左侧、相邻朋友之间和最右侧。随着 $d$ 增大，禁区只会扩大，可用整数点数量单调减少，因此可以二分最大的可行 $d$。

最大平均值问题

最大平均值这一类问题，也可以转化为二分答案来处理，因为比例最值也存在某种答案单调性。

一般来说，我们会尝试消去分母：对于区间 $[l, r]$，需要判定 $\displaystyle \frac{\sum_{i=l}^{r}a_{i}}{r-l+1} \ge x \iff \sum_{i=l}^{r}(a_{i}-x) \ge 0$。

记 $b_{i} = a_{i} - x$，那么就需要判断是否存在区间和大于 $0$ 的合法区间，这就是一个比较简单的判定问题了。

Q6

T7792 最大平均值子段
给定数组，选择一个长度至少为 $d$ 的连续子段，使其平均值最大，并输出一组合法端点。

令 $pre$ 为变换后数组 $b$ 的前缀和。固定右端点 $r$ 时，若区间长度至少为 $d$，对应的左侧前缀位置 $p=l-1$ 满足：$p \le r - d$，区间和为 $pre[r] - pre[p]$。

因此只需要维护所有 $p \le r - d$ 中最小的 $pre[p]$，随着 $r$ 向右移动，合法的前缀候选只会不断增加，所以维护前缀最小值即可完成判定。

Q7

P1419 寻找段落
求长度在 $[S,T]$ 内的最大子段平均值。

本题跟上题的区别在于，它还增加了区间长度上限。

固定右端点 $r$ 后，合法的左侧前缀位置不再是 $p\le r-d$ 这样的不断扩张前缀，而是滑动区间 $p \in [r - T, r - S]$，随着 $r$ 向右移动，旧候选会从左侧失效，新候选会从右侧进入，因此需要用单调队列维护这个滑动窗口中的最小前缀和。

Q8

ABC469E Pro Exam Eligibility
在至少包含 $K$ 场胜利的连续区间中，求最大胜率。

记 $sum_i$ 为胜场数前缀和。对于前缀位置 $l<r$，区间胜率至少为 $x$ 等价于：$\displaystyle \frac{sum_r-sum_l}{r-l}\ge x \iff sum_r - x \cdot r \ge sum_l - x \cdot l$。

记 $f_{i} = sum_{i} - x \cdot i$，同时还需要满足区间包括至少 $K$ 场胜利的要求：$sum_{r} - sum_{l} \ge K$。

随着右端点 $r$ 向右移动，满足这个条件的左端点同样构成不断扩张的前缀。于是可以用双指针依次把新合法的 $l$ 加入候选集合，并维护其中最小的 $f_l$，判断是否存在 $f_r\ge \min f_l$ 即可。

Q9

P3199 最小圈
给一个有向图，找一个环，使得环上边权的平均值 $\displaystyle \frac{\sum w}{|V|}$ 最小，输出最小值。

对于图上的环也是类似的模型，固定平均值 $x$ 后，把每一条边的边权修改为 $w - x$，若存在平均值小于 $x$ 的环，在变换后就会出现负环。

所以本题的二分 check 实际上是图上的负环判定，也可以从分数规划的角度理解。当前笔记库尚未建立独立的 01 分数规划节点，因此暂时保留在本节中。

典型应用

Q10

P1083 借教室
给定 $n$ 天，和 $m$ 份订单。每天有 $r_i$ 个教室，每个订单租借从 $s_j \to t_j$ 的 $d_j$ 个教室。
问：是否有订单会无法完全满足，如果有，第一个不满足的订单是几号。

如果前 $k$ 份订单能够全部满足，那么前 $k-1$ 份订单也一定能够满足；如果前 $k$ 份订单已经无法全部满足，那么任何更长的订单前缀也不可能重新合法，于是订单前缀的可行性具有单调性。

问题就转化为了：如何高效计算前 $k$ 份订单使每天一共被借走了多少教室，然后进行 check。由于涉及很多区间修改，但是只需要在最后统一查询每一天的总需求，所以可以利用差分进行静态处理。

Q11

P1314 聪明的质监员
给定 $n$ 个矿石，每个矿石有重量 $w_i$、价值 $v_i$；另有 $m$ 个检验区间和一个标准值 $S$。

选择阈值 $W$ 后，每个区间的贡献为：

$$y_i= \left(\sum_{j=l_i}^{r_i}[w_j\ge W]\right) \left(\sum_{j=l_i}^{r_i}[w_j\ge W]v_j\right),$$

记 $Y(W)=\displaystyle\sum_{i=1}^{m}y_i$，目标是最小化 $|S-Y(W)|$。

当然如果 $W$ 设置的更高，最终入选的矿石数量就会变少，也就是说，$y$ 的取值是随着 $W$ 的增大而减小的 —— 单调性。

所以可以二分答案，考虑构造 check 函数，目标是通过 $W$ 高效计算 $Y$。我们从柿子入手 $y = \sum_{i=1}^{m}\left[ \sum_{j=l_i}^{r_i}[w_j \geq W] \times \sum_{j=l_i}^{r_i}[w_j \geq W] v_j \right]$。

发现其实 $y_i = cnt_i \times sumv_i$，$cnt_i$ 表示个数，$sumv_i$ 表示价值总和。对于每个固定的 $W$，可以线性构造数量前缀和与价值前缀和，再用它们快速计算所有区间的 $y_i$。这里的前缀和依赖当前阈值，需要在每次 check(W) 中重新构造，并不是只预处理一次。

注：最终目标 $|S-Y(W)|$ 本身并不单调。真正被二分的是单调函数 $Y(W)$ 越过 $S$ 的交界位置，最终答案需要比较交界两侧的候选阈值。

笔记

二分答案不一定直接二分最终目标，也可以寻找某个单调中间量越过目标值的位置。

Q12

P2680 运输计划
给定一棵带权树和若干条运输路径，可以把一条边的权值变为 $0$，使所有运输路径中的最大长度尽量小。

固定最大允许路径长度 $mid$，需要判断是否存在一条边，使其权值变为 $0$ 后，所有运输路径的长度都不超过 $mid$。

对于给定的 $mid$，我们可以将 $M$ 条路径分为两类：

• 长度 $\le mid$ 的路径，记为 $P_1$，这部分不需要处理；
• 长度 $>mid$ 的路径，记为 $P_2$，这部分需要通过把某条边权清零来解决。

为了让所有超限路径都降到 $mid$ 以下，我们选择的边必须满足两个条件：

1. 这条边被所有 $P_2$ 中的路径共同经过，否则至少会有一条超限路径不受影响；
2. 这条边的权值足够大，使最长路径减去它的权值后不超过 $mid$。

第二个条件可以直接根据边权判断。对于第一个条件，可以对所有超限路径进行 树上差分 的边差分，再自底向上汇总差分值。

若某条边的累计经过次数等于超限路径总数，就说明这条边被所有超限路径共同经过，再检查它的边权是否足够即可。

摘要

check 的常见来源

• 直接计数：固定阈值后，计算能够提供多少资源，如 P2440；
• 独立代价求和：计算达到阈值至少需要多少资源，如 P3853；
• 顺序贪心：决策会影响后续结构，如 P1182、P3017、P2678；
• 变换后的前缀信息：把比例、区间或限制转成前缀最值，如最大平均值问题；
• 静态批量统计：固定操作前缀或筛选条件后，用差分、前缀和完成判定，如 P1083、P1314；
• 复合算法判定：固定阈值后，继续调用树上差分或负环判定，如 P2680、P3199。

二分本身只负责寻找边界，check 才保存了原问题的主要结构。

三、小结

所以，二分答案只是把原问题改写成一个参数化判定问题；判定仍然需要回到计数、贪心、前缀和、差分、动态规划、树论或图论中寻找结构。

整数边界

个人常用的 ans 记录法可以直接表达 “找最后一个可行位置”。

▶

整数二分

// 最大可行值 | check 在较小时为真
ll l = lower, r = upper, ans = lower - 1;
while( l <= r ) {
	ll mid = l + ((r - l) >> 1);
	if( check( mid ) ) ans = mid, l = mid + 1;
	else r = mid - 1;
}
// 最小可行值 | check 在较大时为真
ll l = lower, r = upper, ans = upper + 1;
while( l <= r ) {
	ll mid = l + ((r - l) >> 1);
	if( check( mid ) ) ans = mid, r = mid - 1;
	else l = mid + 1;
}

上下界也来自问题结构

• P2440 的答案上界可以取最长原木，若连 $1$ 都不可行则答案为 $0$；
• P1182 的答案至少是最大单项，至多是整个数列之和；
• P3853、P2678 的答案都不会超过公路或河道总长度。

合理收紧区间通常不是二分正确性的必要条件，但能降低无意义判定次数，也能帮助检查自己是否真正理解答案的含义。

实数边界

个人常用的做法是循环固定次数，可以避免浮点条件导致死循环，但输出精度、误差传播与 check 内部的比较仍需单独分析。

▶

实数二分

double l = lower, r = upper;
for( int k = 0; k < 100; ++ k ) {
    double mid = (l + r) / 2.0;
    if( check( mid ) ) l = mid;
    else r = mid;
}
cout << l << '\n';

代码示例

▶

Q0 P2440 木材加工

bool check( int x ) {
    ll cnt = 0;
    for( int i = 1; i <= n; ++ i ) {
        cnt += a[i] / x;
    }
    return cnt >= k;
}

void solve( ) {
    cin >> n >> k;
    for( int i = 1; i <= n; ++ i ) cin >> a[i];

    int l = 1, r = *max_element( a + 1, a + n + 1 ), ans = 0;
    while( l <= r ) {
        int mid = ( l + r ) >> 1;
        if( check( mid ) ) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    cout << ans << '\n';
}

▶

Q1 P1182 数列分段 Section II

bool check( ll x ) {
    ll sum = 0;
    int cnt = 1; // 默认至少有 1 组
    for( int i = 1; i <= n; ++ i ) {
        if( sum + a[i] > x ) {
            sum = a[i];
            cnt ++;
        } else {
            sum += a[i];
        }
    }
    return cnt <= m;
}

void solve( ) {
    cin >> n >> m;
    ll l = 0, r = 0, ans = 0;
    for( int i = 1; i <= n; ++ i ) {
        cin >> a[i];
        l = max( l, a[i] );
        r += a[i];
    }

    while( l <= r ) {
        ll mid = ( l + r ) >> 1;
        if( check( mid ) ) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    cout << ans << '\n';
}

▶

Q2 P3017 Brownie Slicing G

bool check( int mid ) {
    int lst = 0, tot = 0;
    for( int i = 1; i <= r; ++ i ) {
        int s = 0, cnt = 0;
        for( int j = 1; j <= c; ++ j ) {
            s += sum[i][j] - sum[lst][j];
            if( s >= mid ) cnt ++, s = 0;
        }
        if( cnt >= b ) {
            lst = i;
            tot ++;
        }
    }
    return tot >= a;
}

void solve( ) {
    cin >> r >> c;
    cin >> a >> b;
    for( int i = 1; i <= r; ++ i ) {
        for( int j = 1; j <= c; ++ j ) {
            cin >> arr[i][j];
            sum[i][j] = sum[i-1][j] + arr[i][j];
        }
    }

    int ans = 0;
    int l = 0, r = inf;
    while( l <= r ) {
        int mid = ( l + r ) >> 1;
        if( check( mid ) ) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    cout << ans << '\n';
}

▶

Q3 P3853 路标设置

bool check( int x ) {
    int cnt = 0;
    for( int i = 1; i < n; ++ i ) {
        if( a[i+1] - a[i] > x ) {
            cnt += ( a[i+1] - a[i] - 1 ) / x;
        }
    }
    return cnt <= k;
}

void solve( ) {
    cin >> L >> n >> k;
    for( int i = 1; i <= n; ++ i ) cin >> a[i];

    int l = 1, r = L, ans = 0;
    while( l <= r ) {
        int mid = ( l + r ) >> 1;
        if( check( mid ) ) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    cout << ans << '\n';
}

▶

Q4 P2678 跳石头

bool check( int x ) {
    int cnt = 0, last = 0;
    for( int i = 1; i <= n + 1; ++ i ) {
        if( a[i] - last < x ) cnt ++;
        else last = a[i];
    }
    return cnt <= m;
}

void solve( ) {
    cin >> L >> n >> m;
    for( int i = 1; i <= n; ++ i ) cin >> a[i];
    a[n + 1] = L;

    int l = 1, r = L, ans = 0;
    while( l <= r ) {
        int mid = ( l + r ) >> 1;
        if( check( mid ) ) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    cout << ans << '\n';
}

▶

Q5 CF2167E khba Loves to Sleep!

void print( ll l, ll r ) {
    for( ll pos = l; pos <= r && cnt < k; ++ pos ) {
        cout << pos << " ";
        cnt ++;
    }
}

bool check( ll mid ) {
    ll tcnt = 0;
    if( a[1] >= mid ) tcnt += a[1] - mid + 1;
    for( int i = 1; i < n; ++ i ) {
        ll diff = a[i + 1] - a[i];
        if( diff >= mid * 2 ) tcnt += diff - 2 * mid + 1 ;
    }
    if( x - a[n] >= mid ) tcnt += x - a[n] - mid + 1 ;
    return tcnt >= k;
}

void solve( ) {
    cnt = 0;
    cin >> n >> k >> x;
    for( int i = 1; i <= n; ++ i ) cin >> a[i];
    sort( a + 1, a + n + 1 );

    ll l = 0, r = x + 1, ans = 0;
    while( l <= r ) {
        ll mid = ( l + r ) >> 1;
        if( check( mid ) ) ans = mid, l = mid + 1;
        else r = mid - 1;
    }

    if( ans == 0 ) {
        for( int i = 0; i < k; ++ i ) cout << i << " ";
        cout << '\n';
        return;
    }

    if( a[1] >= ans ) print( 0, a[1] - ans );
    
    for( int i = 1; i < n; ++ i ) {
        ll st = a[i] + ans;
        ll ed = a[i+1] - ans;
        if( st <= ed ) print( st, ed );
    }

    if( x - a[n] >= ans ) print( a[n] + ans, x );
    cout << '\n';
}

▶

Q6 T7792 最大平均值子段

int ansl, ansr;
bool check( double x ) {
    sum[0] = 0;
    for( int i = 1; i <= n; ++ i ) {
        sum[i] = sum[i-1] + ( a[i] - x );
    }
    double premin = sum[0];
    int pos = 0;
    for( int r = d; r <= n; ++ r ) {
        int l = r - d;
        if( sum[l] < premin ) {
            premin = sum[l];
            pos = l;
        }
        if( sum[r] - premin >= 0 ) {
            ansl = pos + 1;
            ansr = r;
            return 1;
        }
    }
    return 0;
}

void solve( ) {
    cin >> n >> d;
    for( int i = 1; i <= n; ++ i ) cin >> a[i];
    double l = 0, r = 100;
    ansl = 1, ansr = d;
    for( int t = 1; t <= 100; ++ t ) {
        double mid = ( l + r ) / 2.0;
        if( check( mid ) ) l = mid;
        else r = mid;
    }
    cout << ansl << " " << ansr << '\n';
}

▶

Q7 P1419 寻找段落

bool check( double mid ) {
    sum[0] = 0;
    for( int i = 1; i <= n; ++ i ) {
        sum[i] = sum[i - 1] + ( a[i] - mid );
    }
    deque<int> q;
    for( int i = s; i <= n; ++ i ) {
	    // 入队
        while( !q.empty( ) && sum[ q.back( ) ] >= sum[i - s] ) q.pop_back( );
        q.push_back( i - s );
		// 出队
        while( !q.empty( ) && q.front( ) < i - t ) q.pop_front( );
	    // 统计
        if( !q.empty( ) && sum[i] - sum[ q.front( ) ] >= 0 ) return 1;
    }
    return 0;
}

void solve( ) {
	cin >> n >> s >> t;
    double l = inf, r = -inf;
    for( int i = 1; i <= n; ++ i ) {
        cin >> a[i];
        l = min( l, a[i] );
        r = max( r, a[i] );
    }
	// 实数二分
    for( int k = 1; k <= 100; ++ k ) {
        double mid = ( r + l ) / 2.0;
        if( check( mid ) ) l = mid;
        else r = mid;
    }
    cout << fixed << setprecision(3) << l << '\n';
}

▶

Q8 ABC469E Pro Exam Eligibility

bool check( double mid ) {
    for( int i = 0; i <= n; ++ i ) {
        f[i] = sum[i] - mid * i;
    }

    double mn = inf;
    int l = 0;
    for( int r = 1; r <= n; ++ r ) {
        while( l < r && k <= sum[r] - sum[l] ) {
            mn = min( mn, f[l] );
            l ++;
        }
        if( f[r] >= mn ) return true;
    }
    return false;
}

void solve( ) {
    n = read( ), k = read( );
    string s;
    cin >> s;

    for( int i = 1; i <= n; ++ i ) {
        sum[i] = sum[i - 1] + ( s[i - 1] == 'o' );
    }

    double l = 0, r = 1;
    for( int t = 1; t <= 100; ++ t ) {
        double mid = ( l + r ) / 2.0;
        if( check( mid ) ) l = mid;
        else r = mid;
    }
    cout << fixed << setprecision( 6 ) << l << '\n';
}

▶

Q9 P3199 最小圈

struct Edge {
    int v; double w;
};

vector< Edge > adj[maxn];
double dist[maxn];
bool vis[maxn];
int n, m;

bool has_neg_cycle( int u, double mid ) {
    vis[u] = true;
    for( auto [v, w] : adj[u] ) {
        if( dist[v] > dist[u] + w - mid ) {
            if( vis[v] ) return true;
            dist[v] = dist[u] + w - mid;
            if( has_neg_cycle( v, mid ) ) return true;
        }
    }
    vis[u] = false;
    return false;
}

bool check( double mid ) {
    for( int i = 1; i <= n; ++ i )  {
        dist[i] = 0;
        vis[i] = 0;
    }
    for( int i = 1; i <= n; ++ i ) {
        if( has_neg_cycle( i, mid ) ) return 1;
    }
    return 0;
}

void solve( ) {
    cin >> n >> m;
    for( int i = 1; i <= m; ++ i ) {
        int u, v; double w;
        cin >> u >> v >> w;
        adj[u].push_back({ v, w });
    }
    double l = -1e7, r = 1e7, ans = 0;
    for( int i = 1; i <= 100; ++ i ) {
        double mid = ( l + r ) / 2.0;
        if( check( mid ) ) ans = mid, r = mid;
        else l = mid;
    }
    cout << fixed << setprecision(8) << ans << '\n';
}

▶

Q10 P1083 借教室

ll r[maxn], d[maxn], s[maxn], t[maxn];
ll diff[maxn];
int n, m;

bool check( int k ) {
    memset( diff, 0, sizeof( diff ) );
    for( int i = 1; i <= k; ++ i ) {
        diff[s[i]] += d[i];
        diff[t[i] + 1] -= d[i];
    }
    
    ll sum = 0;
    for( int i = 1; i <= n; ++ i ) {
        sum += diff[i];
        if( sum > r[i] ) return 0;
    }
    return 1;
}

void solve( ) {
    cin >> n >> m;
    for( int i = 1; i <= n; ++ i ) cin >> r[i];
    for( int i = 1; i <= m; ++ i ) cin >> d[i] >> s[i] >> t[i];
	
	// 特殊处理
    if( check( m ) ) {
        cout << 0 << "\n";
        return;
    }
	
    int l = 1, r = m, ans = 0;
    while ( l <= r ) {
        int mid = ( l + r ) >> 1;
        if ( check( mid ) ) l = mid + 1;
        // 这里我们的答案是 不满足条件 的情况！
        else ans = mid, r = mid - 1;
    }

    cout << -1 << "\n" << ans << "\n";
    return;
}

▶

Q11 P1314 聪明的质监员

ll cnt[maxn], sumv[maxn];
int n, m;
ll s;

ll check( ll W ) {
    memset( cnt, 0, sizeof( cnt ) );
    memset( sumv, 0, sizeof( sumv ) );
    for ( int i = 1; i <= n; ++ i ) {
        cnt[i] = cnt[i-1];
        sumv[i] = sumv[i-1];
        if ( w[i] >= W ) {
            cnt[i] += 1;
            sumv[i] += v[i];
        }
    }
    
    ll Y = 0;
    for ( int i = 1; i <= m; ++ i ) {
        Y += ( cnt[R[i]] - cnt[L[i] - 1] ) * ( sumv[R[i]] - sumv[L[i] - 1] );
    }
    return Y;
}

void solve( ) {
    cin >> n >> m >> s;
    ll max_w = 0;
    for( int i = 1; i <= n; ++ i ) {
        cin >> w[i] >> v[i];
        max_w = max( max_w, w[i] );
    }

    for( int i = 1; i <= m; ++ i ) {
        cin >> L[i] >> R[i];
    }

    ll l = 0, r = max_w + 1;
    ll ans = inf;

    while( l <= r ) {
        ll mid = l + ( ( r - l ) >> 1 );
        ll res = check( mid );
        ans = min( ans, abs( res - s ) );
        if( res > s ) l = mid + 1;
        else r = mid - 1;
    }

    cout << ans << "\n";
}

▶

Q12 P2680 运输计划

struct Edge { int v, w; };
vector<Edge> adj[maxn];

int up[maxn][maxlg], dep[maxn];
int dist[maxn], edgew[maxn];

struct Path { int u, v, lca, len; } p[maxn];
int diff[maxn], sum[maxn];
int max_len, max_edge, max_weight;
int n, m;

void dfs( int u, int p, int w ) {
    dep[u] = dep[p] + 1;
    up[u][0] = p;
    dist[u] = dist[p] + w;
    edgew[u] = w;
    for( int i = 1; i < maxlg; ++ i )
        up[u][i] = up[up[u][i - 1]][i - 1];
    for( auto &[v, w] : adj[u] )
        if( v != p ) dfs( v, u, w );
}

int get_lca( int u, int v ) {
    if( dep[u] < dep[v] ) swap( u, v );
    int diff = dep[u] - dep[v];
    for( int i = 0; i < maxlg; ++ i )
        if( ( diff >> i ) & 1 ) u = up[u][i];
    if( u == v ) return u;
    for( int i = maxlg - 1; i >= 0; -- i )
        if( up[u][i] != up[v][i] )
            u = up[u][i], v = up[v][i];
    return up[u][0];
}

void dfs_sum( int u, int p, int cnt ) {
    sum[u] = diff[u];
    for( auto &[v, w] : adj[u] )
        if( v != p ) dfs_sum( v, u, cnt ), sum[u] += sum[v];
    if( sum[u] == cnt ) max_edge = max( max_edge, edgew[u] );
}

bool check( int mid ) {
    int cnt = 0;
    for( int i = 1; i <= n; ++ i ) diff[i] = 0;
    for( int i = 1; i <= m; ++ i ) {
        if( p[i].len <= mid ) continue;
        cnt ++;
        diff[p[i].u] ++, diff[p[i].v] ++;
        diff[p[i].lca] -= 2;
    }
    if( cnt == 0 ) return 1;
    max_edge = 0;
    dfs_sum( 1, 0, cnt );
    return max_len - max_edge <= mid;
}

void solve( ) {
    n = read( ), m = read( );
    for( int i = 1; i <= n - 1; ++ i ) {
        int u = read( ), v = read( ), w = read( );
        adj[u].push_back({ v, w });
        adj[v].push_back({ u, w });
        max_weight = max( max_weight, w );
    }

    dfs( 1, 0, 0 );
    for( int i = 1; i <= m; ++ i ) {
        p[i].u = read( ), p[i].v = read( );
        p[i].lca = get_lca( p[i].u, p[i].v );
        p[i].len = dist[p[i].u] + dist[p[i].v] - 2 * dist[p[i].lca];
        max_len = max( max_len, p[i].len );
    }

    int l = max( 0, max_len - max_weight ), r = max_len, ans = max_len;
    while( l <= r ) {
        int mid = ( l + r ) >> 1;
        if( check( mid ) ) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    cout << ans << '\n';
    return 0;
}