第六章:二分与倍增

当候选答案能按顺序排列,且一次判断可以排除连续的一半候选时,就可以使用二分。本章先从有序数组查找建立区间不变量,再把查找对象换成答案;最后用倍增预存较长的连续跳跃,减少重复移动。

阅读前需要掌握有序数组、循环和整数范围;综合题还会调用第四章的前缀和与差分。本章各个 C++ 程序均可独立编译,不能把多个 main\texttt{main} 拼成一份源文件。倍增使用固定后继关系,步数的二进制拆分在本节说明。

1. 查找指定值

例题:查找。

简易题面:给定单调不减序列和若干询问,输出每个询问值第一次出现的下标,不存在则输出 −1-1。

数据范围:1≤n≤1061\le n\le10^6,1≤m≤1051\le m\le10^5;0≤ai,qi≤1090\le a_i,q_i\le10^9。

顺序查找每次最多访问全部元素。有序数组允许从中点比较:若中点偏小,左半不可能包含目标;若偏大,右半不可能包含目标。先手算返回任意匹配位置的基础过程,再改成例题要求的首次出现位置。全局数组 a[1]a[1] 至 a[n]a[n] 已非降序排列,xx 为当前询问值,ans=−1ans = -1 表示尚未找到。

前提是数组已经有序。使用 l+(r-l)/2\texttt{l+(r-l)/2} 可以避免 l+rl+r 溢出。

循环中的 [l,r][l,r] 表示尚未被排除的候选位置。若中点太小,有序性保证 [l,mid][l,mid] 全部太小;若中点太大,[mid,r][mid,r] 全部太大。把中点一并排除,区间才能严格缩短。

可以把候选区间想成一排按数值排好序、尚未划掉的卡片。检查中间一张后,划掉的是一整段,而不是只划掉这一张。例如在 [1,3,5,7,9,11,13,15][1,3,5,7,9,11,13,15] 中查找 1313:

轮次检查前的下标范围中点与比较排除的位置剩余位置
11[1,8][1,8]mid=4mid=4,a[4]=7<13a[4]=7<13[1,4][1,4]:值都不超过 77[5,8][5,8]
22[5,8][5,8]mid=6mid=6,a[6]=11<13a[6]=11<13[5,6][5,6]:值都不超过 1111[7,8][7,8]
33[7,8][7,8]mid=7mid=7,a[7]=13a[7]=13不再排除,直接返回答案下标为 77

在有序数组中查找 13:依次检查下标 4、6、7,最终找到目标

灰色卡片表示已经排除的位置,蓝色范围表示待查区间。每次未找到目标时,候选数至多减为原来的一半,因此最多进行 O(log⁡n)O(\log n) 轮检查。

下面的完整演示程序读入 n,mn,m、有序数组和 mm 个查询值,每行输出一个匹配位置或 −1-1。它用于观察基本查找过程;题目要求的首次位置由下一节实现。

#include <bits/stdc++.h>
using namespace std;
const int N=1000000+10;
int n,a[N];
int get(int x){
    int l=1,r=n,ans=-1;
    while(l<=r){
        int mid=l+(r-l)/2;
        if(a[mid]==x){
            ans=mid;
            break;
        }
        if(a[mid]<x)l=mid+1;
        else r=mid-1;
    }
    return ans;
}
int main(){
    int m,x;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    while(m--){
        scanf("%d",&x);
        printf("%d\n",get(x));
    }
    return 0;
}

这个程序遇到相等值就结束,所以有重复元素时不保证返回第一次出现的位置。例题 查找 要求首次出现,应继续寻找左边界。若根本不存在,循环结束后仍为 ans=−1ans=-1,不要把最终中点当成答案。

当边界允许跨越很大的正负范围时,r−lr-l 本身也可能超出 int\texttt{int},仍需要让边界变量使用足够宽的类型;中点写法不能替代范围分析。

2. 查找第一个满足条件的位置

假设条件随位置变化为:

false false false true true true

把 ansans 初值设为 n+1n+1,表示还没有见过真值。找到可行位置后先保存,再继续向左寻找第一个。对于首次出现问题,令 check(mid)\texttt{check(mid)} 等价于 a[mid]≥xa[mid]\ge x;搜索结束后,还需检查 ans≤n∧a[ans]=xans\le n\land a[ans]=x,否则应输出无解。每次查询使用新的 l,r,ansl,r,ans,时间为 O(log⁡n)O(\log n)。

查找最后一个满足条件的位置时,方向相反。

把“第一个真”看成一个尚待定位的分界线。检查到真时,中点先作为备选答案保存,之后只在左半继续找更早的真;检查到假时,中点及其左侧都可以排除。结束时,ansans 要么是最早的真,要么保留哨兵 n+1n+1 表示一个都没有。

例如真假序列为 假,假,真,真,真,初始 [1,5][1,5]:检查 3 为真,记住 3,改查 [1,2][1,2];再检查 1、2 均为假,最终答案仍是 3。候选位置被排除后,已记录的答案不会丢失。

重复值能展示“找到一个”与“找到第一个”的区别。在 [1,2,2,2,5][1,2,2,2,5] 中查询 22,第一次检查下标 33 就已经相等;但它左侧还有一个 22,所以不能立即结束。把条件写成 a[mid]≥2a[mid]\ge 2,得到的真假排列为“假、真、真、真、真”:

轮次检查前的范围判断结果保存的答案下一轮范围
11[1,5][1,5]mid=3mid=3,条件为真ans=3ans=3[1,2][1,2]
22[1,2][1,2]mid=1mid=1,条件为假ans=3ans=3[2,2][2,2]
33[2,2][2,2]mid=2mid=2,条件为真ans=2ans=2[2,1][2,1],区间为空

查找第一个大于等于 2 的位置:先保存下标 3,再向左找到下标 2

第一次保存答案后,下标 33 已在待查范围之外,但答案标记仍然保留。这里 r=mid−1r=mid-1 的前提是已经执行了 ans=midans=mid;若只排除中点而不保存,就可能丢失答案。

“最后一个真”常对应 真...真,假...假:真时保存并向右找,假时向左找。应先画出真假排列,再决定移动方向,而不是只改一个比较符号。

循环开始时,真正的左边界若存在,要么是已保存的 ansans,要么仍在待查闭区间 [l,r][l,r] 中。真时保存中点再删去右半,假时删去左半,都不会丢掉这两处之外的新答案;区间清空后,只需检查保存的位置。下面的程序与《查找》的输入输出一致。

#include <bits/stdc++.h>
using namespace std;
const int N=1000000+10;
int n,a[N];
int get(int x){
    int l=1,r=n,ans=n+1;
    while(l<=r){
        int mid=l+(r-l)/2;
        if(a[mid]>=x){
            ans=mid;
            r=mid-1;
        }else l=mid+1;
    }
    if(ans<=n&&a[ans]==x)return ans;
    return -1;
}
int main(){
    int m,x;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    for(int i=1;i<=m;++i){
        scanf("%d",&x);
        printf("%d%c",get(x),i==m?'\n':' ');
    }
    return 0;
}

若要找最后一个不大于 xx 的位置,条件应是 ai≤xa_i\le x,真假排列为“真到假”。取 ans=0ans=0,真时保存 midmid 并令 l=mid+1l=mid+1,假时令 r=mid−1r=mid-1。例如 [1,2,2,2,5][1,2,2,2,5] 查询 22:先检查位置 33,保存 33;再检查 44,保存 44;最后检查 55 为假,答案为 44。全为假时保留哨兵 00。这不是寻找首次出现时直接换掉一个比较符号,而是重新确认目标分界与移动方向。

3. STL 边界函数

以下仍查询同一个有序全局数组。返回位置减去数组起始地址 aa 后得到一号下标(不是减去搜索起点 a+1a+1);n+1n+1 是尾后位置,只能比较,不能作为有效元素读取。

  • lower_bound\texttt{lower\_bound}:第一个大于等于 xx;
  • upper_bound\texttt{upper\_bound}:第一个大于 xx;
  • p2−p1p2-p1:xx 的出现次数。

返回位置可能是 n+1n+1,使用前必须判断。

数组 [1,2,2,2,5][1,2,2,2,5] 中查询 22,p1=2p1=2、p2=5p2=5,出现次数为 33。查询不存在的 33,两个位置都为 55,差为零;查询 66,两个位置都为 n+1n+1。

查找第一个严格大于 2 的位置:排除相等元素,最终返回下标 5

目标同为 22 时,三个值为 22 的位置在 a[mid]≥2a[mid]\ge 2 下都为真,在 a[mid]>2a[mid]>2 下都为假。因此两个分界点分别落在下标 22 和 55,相等元素恰好占据半开区间 [2,5)[2,5)。这两幅动图使用手写二分展示边界的含义,不表示 STL 函数必须按相同顺序访问元素。

要判断值是否存在,应先检查 p1≤np1\le n,再检查 a[p1]=xa[p1]=x。lower_bound\texttt{lower\_bound} 返回的是“不小于目标”的边界,目标缺失时也会正常返回一个位置。调用前必须保证数组按相容的比较规则有序。

下面是边界函数的独立演示:输入与上一节相同,每次查询输出下界位置、上界位置、出现次数。输出的 n+1n+1 表示尾后位置,不读取该处元素。

#include <bits/stdc++.h>
using namespace std;
const int N=1000000+10;
int a[N];
int main(){
    int n,m,x;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    while(m--){
        scanf("%d",&x);
        int p1=lower_bound(a+1,a+n+1,x)-a;
        int p2=upper_bound(a+1,a+n+1,x)-a;
        printf("%d %d %d\n",p1,p2,p2-p1);
    }
    return 0;
}

4. 二分答案

例题:数列分段 Section II。

简易题面:将长度为 nn 的非负整数序列分成恰好 mm 个非空连续段,使各段元素和的最大值最小。输出这个最小值。

数据范围:1≤m≤n≤1051\le m\le n\le10^5;0≤ai<1080\le a_i<10^8,答案不超过 10910^9。

直接选择 m−1m-1 个切分位置,会产生大量方案。逐个构造最优划分较难,但给定一个段和上限后,只需判断能否在规定段数内装下全部元素。于是可以把求最优值改成判定,再寻找最小可行上限。

把非负序列切成 mm 个非空连续段,最小化最大段和。最小候选至少是单个元素最大值,最大候选可以取全体总和;上界的类型要容纳总和,不能只看最后输出答案的范围。

给定段和上限 xx,从左到右尽量把元素放入当前段,只有再放一个就超限时才开新段。

为什么这会使段数最少?记贪心完成第 jj 段后的右端为 gjg_j,任意合法划分对应的右端为 ojo_j。第一段尽量向右延伸,所以 g1≥o1g_1\ge o_1。贪心若已经覆盖全部元素,就不需要再开新段。

在尚未完成覆盖时,假定 gj−1≥oj−1g_{j-1}\ge o_{j-1}:若 gj−1≥ojg_{j-1}\ge o_j,贪心用前 j−1j-1 段已经覆盖到对方第 jj 段的末尾;否则,区间 [gj−1+1,oj][g_{j-1}+1,o_j] 是对方第 jj 段的一部分。元素非负,这一部分的和不会超过整段的上限 xx,贪心第 jj 段至少能覆盖到 ojo_j。

因此同样多的段数下,贪心总能覆盖得至少一样远;任意划分覆盖全数组时,贪心也已覆盖全数组,所需段数不会更多。

例如 [7,2,5,10,8][7,2,5,10,8] 切两段:上限 1717 时,贪心得到 [7,2,5][7,2,5]、[10][10]、[8][8] 三段,不可行;上限 1818 时得到 [7,2,5][7,2,5]、[10,8][10,8] 两段,可行。上限增加只会放宽限制,因此可以找第一个可行值。

这个模型可以想成沿着传送带装箱:元素必须按原顺序装入,每箱容量都是待检查的上限 xx,当前箱再放一个就超限时才换箱。容量增大后,原来能装下的方案仍然能装下,因此可行性只会从假变真。

二分段和上限:依次试用 21、15、18、17,每轮重新分段,最终得到 18

上方数轴表示候选上限 1010 至 3232,下方按顺序放入 [7,2,5,10,8][7,2,5,10,8]。每次取中点后,重新分段,再用所需段数判断上限是否可行。搜索的是容量,不是元素下标。

判定只需检查段数不超过 mm:元素非负,拆开任意已有段不会增大段和,而且 m≤nm\le n 时总能继续拆到恰好 mm 个非空段。若允许负数,贪心和这个拆分论证都需要重新检查。每次 check\texttt{check} 都从空段状态开始,不能继承上次候选的计数。

程序用全局 int a[100010], n, m\texttt{int a[100010], n, m} 保存输入。元素和可能接近 101310^{13},因此二分边界、候选值及段内累计和都使用 long long\texttt{long long},即使题面保证最终答案不超过 10910^9。

取 ll 为最大元素、rr 为元素总和,便得到包含答案且右端可行的闭区间。下面每轮都保留最小可行值所在的一侧,结束时两端相等。

当所有元素都为零时,初始 l=r=0l = r = 0,无需进入循环,答案就是零。总时间为 O(nlog⁡(V+2))O(n\log(V+2)),其中 VV 是搜索范围宽度;输入数组占 O(n)O(n) 空间。

对上面的五个数,要求恰好分成两段时,完整的区间变化如下:

检查前的候选上限范围试用上限贪心分段判定结果更新后的范围
[10,32][10,32]2121[7,2,5][7,2,5]、[10,8][10,8]两段,可行[10,21][10,21]
[10,21][10,21]1515[7,2,5][7,2,5]、[10][10]、[8][8]三段,不可行[16,21][16,21]
[16,21][16,21]1818[7,2,5][7,2,5]、[10,8][10,8]两段,可行[16,18][16,18]
[16,18][16,18]1717[7,2,5][7,2,5]、[10][10]、[8][8]三段,不可行[18,18][18,18]

这里判定为真时使用 r=midr=mid,与前面的 r=mid−1r=mid-1 并不矛盾:前一种写法把中点存入 ansans 后继续搜索,本节写法则让答案始终留在 [l,r][l,r] 内,没有另存答案。若把本节的更新直接改成 r=mid−1r=mid-1,第三轮就会丢掉正确答案 1818。

若要求的段数改为 11 或 55:只有一段时,答案为总和 3232;每个元素单独一段时,答案为最大元素 1010。这两个边界例子也说明了初始范围的两个端点分别来自哪里。

把手算的两层工作对应到程序:check\texttt{check} 负责一个容量下的完整分段,main\texttt{main} 只负责缩小容量范围。输入第一行为 n,mn,m,第二行为数组,输出最小的最大段和。

#include <bits/stdc++.h>
using namespace std;
const int N=100000+10;
int n,m,a[N];
bool check(long long x){
    int cnt=1;
    long long sum=0;
    for(int i=1;i<=n;++i){
        if(a[i]>x)return 0;
        if(sum+a[i]>x){
            ++cnt;
            sum=0;
        }
        sum+=a[i];
    }
    return cnt<=m;
}
int main(){
    scanf("%d%d",&n,&m);
    long long l=0,r=0;
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        l=max(l,1LL*a[i]);
        r+=a[i];
    }
    while(l<r){
        long long mid=l+(r-l)/2;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    printf("%lld\n",l);
    return 0;
}

5. 实数二分

简单问题:给定 0≤n≤10120\le n\le10^{12},求非负平方根,绝对误差不超过 10−610^{-6}。

按很小的步长枚举答案,会使次数随精度要求急剧增加。非负数平方随数值增大而增大,因此可以比较中点的平方与 nn,每次排除一半范围。答案位于 [0,max⁡(1,n)][0,\max(1,n)],程序中的 l,r,nl,r,n 均为 double\texttt{double}。

先手算 n=2n=2:初始 [0,2][0,2];中点 11 的平方偏小,留下 [1,2][1,2];中点 1.51.5 的平方偏大,留下 [1,1.5][1,1.5];中点 1.251.25 的平方偏小,留下 [1.25,1.5][1.25,1.5]。每次都保留平方根所在的一半。

理想实数运算中,迭代 tt 次后区间宽度缩小为原来的 2−t2^{-t}。本例迭代次数足够,答案也不超过 10610^6,double\texttt{double} 能满足所需绝对精度。输出仍要保留足够小数位。实数更新不使用整数二分中的加一、减一;固定次数也能避免端点因浮点舍入不再变化时陷入死循环。

连续函数求根还有另一种二分依据:两端异号时,保留仍然异号的一半。它依赖连续性,不要求整个函数单调;但多根区间只能保证夹住某个根。三次方程等问题必须先分析根的范围与分离条件,不能直接套一个全局单调判定。

下面程序的输入是一个非负实数,输出它的平方根:

#include <bits/stdc++.h>
using namespace std;
int main(){
    double n;
    cin>>n;
    double l=0,r=max(1.0,n);
    for(int t=1;t<=100;++t){
        double mid=l+(r-l)/2;
        if(mid*mid>=n)r=mid;
        else l=mid;
    }
    printf("%.10f\n",(l+r)/2);
    return 0;
}

即使理想区间宽度能达到 1012/210010^{12}/2^{100},实际精度仍受 double\texttt{double} 舍入限制,不能承诺任意位数。这里根至多为 10610^6,该量级相邻浮点数的距离远小于 10−610^{-6},十位小数也足以控制输出舍入。本程序没有使用“函数值差足够小”作为停止条件,因为函数值误差与横坐标误差不是同一件事。

6. 倍增

简单问题:远程跳转。

简易题面:有 nn 个传送点,编号为 11 到 nn。从传送点 ii 进行一次传送后,会到达 nxtinxt_i。

给定 qq 次询问。每次询问给出起点 xx 和非负整数 kk,请输出从 xx 出发恰好传送 kk 次后所在的传送点。

数据范围:1≤n,q≤2×1051 \le n,q \le 2\times 10^5;1≤nxti,x≤n1 \le nxt_i,x \le n;0≤k≤10180 \le k \le 10^18。

逐次模拟每条询问,步数可能达到十亿以上。一步规则固定时,可以预先保存大步跳转,查询时再拼接。程序用 nxt[i][k]nxt[i][k] 保存从位置 ii 连续走 2k2^k 步后的位置。连续两段 2k−12^{k-1} 步正好拼成一段 2k2^k 步,因此可以逐层建表。全局 int nxt[200010][60]\texttt{int nxt[200010][60]} 保存跳转表,约需 4848 MB;第 00 层保存每个位置的一步后继。

查询时 ss 为非负 long long\texttt{long long},且 s≤1018s\le10^{18} 时预留 6060 层即可。xx 初始为查询起点。每轮用整除 22 和取余 22 提取二进制位:余数为一,就走当前层对应的步数。

零步查询直接保留起点,不进入循环。

把走 1313 步写成 8+4+18+4+1 步,只需完成三次已经预处理好的跳转。nxt[i][k]nxt[i][k] 的计算先走前半段 2k−12^{k-1} 步,再从中途位置继续走同样多的步,因此右侧两个表项都来自较低层。预处理必须先枚举层数,再枚举全部位置。

若最大步数为 KK,表的时间、空间均为 O(nlog⁡(K+2))O(n\log(K+2)),单次查询为 O(log⁡(K+2))O(\log(K+2));层数取决于步数,而不只是位置个数。K≤1018K\le 10^18 时需要覆盖第 00 至 5959 位,步数使用 long long\texttt{long long}。若允许走到不存在的位置,可用 00 作哨兵,并令它在所有层仍跳到 00。

下面手算一个有环的例子:1→2→3→4→21\to2\to3\to4\to2。从 11 出发,走 1,2,4,81,2,4,8 步分别到 2,3,2,32,3,2,3。例如四步跳转先查 nxt[1][1]=3nxt[1][1]=3,再查 nxt[3][1]=2nxt[3][1]=2,得到 nxt[1][2]=2nxt[1][2]=2。查询 13=1+4+813=1+4+8 步时,按低位到高位先从 11 跳一步到 22,再从 22 跳四步到 33,最后从 33 跳八步到 22。每次查表必须使用上一次跳转后的起点。

倍增:四个点的一步关系,及从 1 出发按 1、4、8 步拼接的查询

代码第一行输入 n,qn,q,第二行输入各点一步后继,随后每行输入起点和步数。

#include <bits/stdc++.h>
using namespace std;
const int N=200000+10;
int nxt[N][60];
int main(){
    int n,q,x;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;++i)scanf("%d",&nxt[i][0]);
    for(int k=1;k<60;++k){
        for(int i=1;i<=n;++i)nxt[i][k]=nxt[nxt[i][k-1]][k-1];
    }
    while(q--){
        long long s;
        scanf("%d%lld",&x,&s);
        for(int k=0;s>0;++k,s/=2){
            if(s%2==1)x=nxt[x][k];
        }
        printf("%d\n",x);
    }
    return 0;
}

建表的正确性可以逐层说明:第 00 层来自输入;若第 k−1k-1 层正确,先后两次这样的跳转就恰好走了 2k2^k 步。查询始终保证当前位置已完成所有处理过的二进制位对应的总步数,最终所有位处理完毕,走过的步数正好等于原询问值。图中虽然有环,仍不影响“恰好走若干步”的含义。

第七章的快速幂也按二进制拆分次数,但它反复平方一个数值、把选中的幂乘入答案;这里预先合成的是所有起点的后继函数。共同点是把长过程拆成二的幂次长度,维护的对象不同。

7. 二分综合模型

7.1 二分操作前缀

例题:NOIP 2012 提高组·借教室。

简易题面:按顺序处理 mm 次教室申请,每次在闭区间 [si,ti][s_i,t_i] 的每天占用 did_i 间。给出每天容量,求第一个无法满足的申请;全部成功则输出 00。

数据范围:1≤n,m≤1061\le n,m\le10^6,0≤ri,di≤1090\le r_i,d_i\le10^9,1≤si≤ti≤n1\le s_i\le t_i\le n。

若执行前 kk 个操作后的状态可以快速检查,而且一旦失败,执行更多操作也一定失败,就可以二分第一个失败的操作。

前 kk 次资源申请可以用差分批量累计,再检查任一天是否超额。申请量非负,因此一旦前 kk 次已经失败,增加后续申请不可能重新成功,失败条件具有单调性。

每次检查都要清空本次累计数组并只加入前 kk 次申请。二分尝试的 kk 不按大小顺序出现,不能默认下一次检查只是给上一次状态追加操作。还应先区分“全部成功”和“存在首次失败”两种输出。

先手算三天容量 [3,2,3][3,2,3],按顺序申请“第 11 至 22 天各借 22 间”“第 22 至 33 天各借 11 间”“第 33 天借 11 间”。检查前一份时,用量为 [2,2,0][2,2,0],可满足;检查前两份时,用量为 [2,3,1][2,3,1],第二天超额。第三份不会减少第二天用量,因此首次失败是第 22 份。这里二分下标是申请编号,差分下标却是日期,二者不能混用。

申请前缀判定:前一份可行,前两份在第二天超过容量

先检查全部 mm 份。如果可行,直接输出 00;否则已知首次失败存在,保持它在 [l,r][l,r] 内。中点可行说明首次失败在它右侧;中点失败则保留中点及左侧。这正是前面“答案保留在区间中”的版本。每次差分还原得到的是真实用量,判定遍历全部日期,所以既不会漏掉超额日期,也不会凭空制造冲突。

输入格式与原题一致,失败时输出两行 −1-1 和编号。一次检查耗时 O(n+k)O(n+k),总时间 O((n+m)log⁡(m+1))O((n+m)\log(m+1)),空间 O(n+m)O(n+m)。同一天累计申请最多为 101510^{15},差分与还原和使用 long long\texttt{long long};只用 int\texttt{int} 保存单份申请量并不能保证累计值安全。

#include <bits/stdc++.h>
using namespace std;
const int N=1000000+10;
int n,a[N],d[N],s[N],t[N];
long long b[N];
bool check(int k){
    fill(b,b+n+2,0);
    for(int i=1;i<=k;++i){
        b[s[i]]+=d[i];
        b[t[i]+1]-=d[i];
    }
    long long sum=0;
    for(int i=1;i<=n;++i){
        sum+=b[i];
        if(sum>a[i])return 0;
    }
    return 1;
}
int main(){
    int m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    for(int i=1;i<=m;++i)scanf("%d%d%d",&d[i],&s[i],&t[i]);
    if(check(m)){puts("0");return 0;}
    int l=1,r=m;
    while(l<r){
        int mid=l+(r-l)/2;
        if(check(mid))l=mid+1;
        else r=mid;
    }
    printf("-1\n%d\n",l);
    return 0;
}

7.2 隐式序列第 kk 小

简单问题:乘法表第 K 小。

简易题面:有一个 nn 行 mm 列的乘法表,第 ii 行第 jj 列的数为 i×ji\times j。

把表中的 n×mn\times m 个数按非递减顺序排列,相同的数按出现次数重复保留。求排列后的第 kk 个数。

数据范围:1≤n,m≤5×1051\le n,m\le 5\times 10^5;1≤k≤n×m1\le k\le n\times m。

有些有序序列太大,不能完整生成。可以二分候选值 xx,计算“小于等于 xx 的元素个数”,再寻找第一个计数达到 kk 的值。

乘法表第 ii 行为 i,2i,…,mii,2i,\ldots,mi,其中不超过 xx 的个数是 min⁡(m,⌊x/i⌋)\min(m,\lfloor x/i\rfloor)。对全部行求和,就能知道整个表中不超过 xx 的元素数,无须生成 nmnm 个元素。

重复值按出现次数计数。寻找第一个“计数至少为 kk”的 xx,才能正确处理多个位置拥有同一个值的情况;不能要求计数恰好等于 kk,因为计数可能一次跳过 kk。

例如 3×33\times3 表为 [1,2,3][1,2,3]、[2,4,6][2,4,6]、[3,6,9][3,6,9]。排序后是 [1,2,2,3,3,4,6,6,9][1,2,2,3,3,4,6,6,9],第 44 小是 33。候选 22 的三行计数为 2,1,02,1,0,合计 33;候选 33 的计数为 3,1,13,1,1,合计 55。计数从 33 跳到 55,没有“恰好四个”的候选值。

把候选值增加时,每行满足上限的列只会增多,所以总计数不减。若第 kk 小值为 vv,所有 x<vx<v 都不足 kk 个,所有 x≥vx\ge v 都至少有 kk 个,最早为真的整数恰好是 vv。初始范围为 [1,nm][1,nm],必含答案。行列可以交换,枚举较短维能减少判定次数。

输入一行 n,m,kn,m,k,输出第 kk 小值。nmnm 可达 2.5×10112.5\times10^{11},范围、排名和累计数量都使用 long long\texttt{long long};数组没有实际建立。总时间为 O(min⁡(n,m)log⁡(nm))O(\min(n,m)\log(nm)),额外空间 O(1)O(1)。

#include <bits/stdc++.h>
using namespace std;
long long n,m,k;
bool check(long long x){
    long long sum=0;
    for(long long i=1;i<=n;++i){
        sum+=min(m,x/i);
        if(sum>=k)return 1;
    }
    return 0;
}
int main(){
    cin>>n>>m>>k;
    if(n>m)swap(n,m);
    long long l=1,r=n*m;
    while(l<r){
        long long mid=l+(r-l)/2;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    cout<<l<<'\n';
    return 0;
}

7.3 平均值参数化

简单问题:最大平均数。

简易题面:给定一个长度为 nn 的非负整数序列 a1,a2,…,ana_1,a_2,\ldots,a_n。请选择一个长度不少于 mm 的连续子段,使这个子段的平均数尽可能大。

输出最大平均数乘以 10001000 后向下取整的结果。

数据范围:1≤m≤n≤1051\le m\le n\le 10^5;0≤ai≤20000\le a_i\le 2000。

直接枚举两个端点并求平均数,即使有前缀和也要枚举 O(n2)O(n^2) 个区间。若先给定平均数门槛 xx,长度为 dd、元素和为 SS 的区间满足 S/d≥xS/d\ge x,等价于 S−dx≥0S-dx\ge0。因此把每个元素减去 xx,便只需寻找长度至少为 mm、和非负的区间。

本题要求输出向下取整后的千倍平均数,可以直接搜索整数 XX,并把每个数变为 1000ai−X1000a_i-X。某个区间变换后的和非负,当且仅当它的千倍平均数至少为 XX。最大的可行整数就是所求的向下取整结果,不需要在二分结束后猜测怎样修正浮点误差。

设变换后的前缀和为 sis_i,并令 s0=0s_0=0。以 rr 为右端时,左端可以写成 j+1j+1,长度限制成为 j≤r−mj\le r-m。于是只需判断

sr−min⁡0≤j≤r−msj≥0.s_r-\min_{0\le j\le r-m}s_j\ge0.

扫描 r=m,m+1,…,nr=m,m+1,\ldots,n,每轮新加入的合法前缀位置只有 r−mr-m。维护这些合法位置的最小值 mnmn,不需要重新枚举全部左端点。

例如 a=[1,4,4,1]a=[1,4,4,1],要求长度至少为 22。试 X=4000X=4000,变换值为 [−3000,0,0,−3000][-3000,0,0,-3000],前缀和为 [0,−3000,−3000,−3000,−6000][0,-3000,-3000,-3000,-6000]:

右端 rr新加入的前缀位置合法前缀最小值sr−mns_r-mn判断
220000−3000-3000不可行
3311−3000-300000区间 [2,3][2,3] 可行

平均数门槛:右端为 3 时只允许使用前缀位置 0、1

右端为 33 时,程序先把 s1s_1 加入候选,再计算差,才能找到 [2,3][2,3]。如果把 s3s_3 也加入候选,就可能拿到长度为零的伪区间;如果只计算最近 mm 个元素,则会漏掉更长区间。例如 [4,1,4][4,1,4]、m=2m=2 的两个长度为 22 的平均数都是 2.52.5,整个长度为 33 的区间平均数却为 33。

门槛越大,变换后每个元素越小,可行性只能从真变假。保持最大可行整数位于闭区间 [l,r][l,r],初始 [0,2000000][0,2000000]。中点可行时保留中点并向右找,否则删去中点及右边。这里用上取整中点:若 r=l+1r=l+1,取下取整中点会使可行分支反复执行 l=ll=l;上取整保证区间严格缩短。

输入第一行 n,mn,m,第二行数组。前缀和绝对值最多 2×10112\times10^{11},使用 long long\texttt{long long}。每次检查 O(n)O(n),二分约 2121 次,总时间 O(nlog⁡2000001)O(n\log 2000001),空间 O(n)O(n)。下面的程序完全使用整数计算。

#include <bits/stdc++.h>
using namespace std;
const int N=100000+10;
int n,m,a[N];
long long s[N];
bool check(int x){
    s[0]=0;
    for(int i=1;i<=n;++i)s[i]=s[i-1]+1000LL*a[i]-x;
    long long mn=0;
    for(int r=m;r<=n;++r){
        mn=min(mn,s[r-m]);
        if(s[r]-mn>=0)return 1;
    }
    return 0;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    int l=0,r=2000000;
    while(l<r){
        int mid=l+(r-l+1)/2;
        if(check(mid))l=mid;
        else r=mid-1;
    }
    printf("%d\n",l);
    return 0;
}

8. 作业

巩固练习

提高训练

留言

可以匿名留言,无需注册或登录。昵称和邮箱均可不填,邮箱不会公开显示。