导语
以下为欢乐赛#85的题解，最后两道题对于数学和代码构建能力有了一定要求，如果你有着不错的思维和代码实现能力，那么在学完语法阶段后，是可以做出最后两题的。
可以在帖子下面留言相关建议与难度调整建议，若采纳会给予回复。
目录
名字 难度 知识点 A 卡片入框 入门 分支结构、逻辑运算符 B 最长纸带 入门 循环结构、分支结构 C 三格合计 入门 一维数组、循环结构 D 接龙断点 入门 字符串、循环结构 E 竖直落珠 普及- 一维数组、循环嵌套 F 彩带对齐 普及- 枚举、一维数组 G 最近刻度 普及- sort排序、一维数组 H 连续整数拼和 普及- 枚举、算术运算符
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
A 卡片入框
题意简述
输入一行四个整数 h,w,a,bh,w,a,bh,w,a,b，依次表示框的高、框的宽、卡片原来的高和宽，满足 1≤h,w,a,b≤1091\le h,w,a,b\le10^91≤h,w,a,b≤109。卡片可以保持原方向，也可以旋转四分之一圈，边缘重合允许放入。
按优先顺序输出结果：原方向可放入时输出 111；否则旋转后可放入时输出 222；两个方向都放不入时输出 000。
样例 #1 中，框高为 333、宽为 555，卡片高为 444、宽为 222。原方向超过框高，旋转后高为 222、宽为 444，所以输出 222。
解题思路
题意分析
原方向放入时，高和宽需要同时满足 a≤ha\le ha≤h、b≤wb\le wb≤w。旋转后卡片的高、宽交换，条件变为 b≤hb\le hb≤h、a≤wa\le wa≤w。
题目要求优先保持原方向，所以先判断原方向。这个条件失败后，再判断旋转方向。最后剩下的情况就是两个方向都无法放入。每个长度至多为 10910^9109，代码只比较长度，使用普通整数即可。
部分分说明：
* 测试点 1∼101\sim101∼10（全量数据，每点 101010 分）：按上述顺序判断两个方向，使用完整的三分支算法；本题采用普通逐点计分。
实现步骤
1. 读入框和卡片的四个长度。
2. 如果 a≤ha\le ha≤h 且 b≤wb\le wb≤w，输出 111。
3. 否则，如果 b≤hb\le hb≤h 且 a≤wa\le wa≤w，输出 222。
4. 否则，输出 000。
正确性说明
卡片边缘与框边平行时，卡片高和宽分别不超过框的对应长度，就是放入的充要条件。程序首先检查原方向的充要条件，成功时按优先规则输出 111；失败后检查旋转方向的充要条件，成功时输出 222；两种条件都失败时输出 000。因此所有情况下输出都符合题目规则。
复杂度分析
程序只进行常数次比较，时间复杂度为 O(1)O(1)O(1)，额外空间复杂度为 O(1)O(1)O(1)。
参考代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
B 最长纸带
题意简述
第一行输入纸带根数 nnn，第二行输入 nnn 根纸带的长度 a1,a2,…,ana_1,a_2,\ldots,a_na1 ,a2 ,…,an 。满足 1≤n≤1000001\le n\le1000001≤n≤100000，1≤ai≤1091\le a_i\le10^91≤ai ≤109。
输出一个整数，表示最长纸带的长度。即使有多根纸带并列最长，也只输出这个长度一次。
样例 #1 的五个长度为 3,8,5,8,23,8,5,8,23,8,5,8,2，最大长度是 888，所以输出 888。
解题思路
题意分析
用变量 mx\mathrm{mx}mx 记录已经读入的纸带中的最大长度。每读到一根新纸带，设长度为 xxx，将它与 mx\mathrm{mx}mx 比较；如果 xxx 更大，就把 mx\mathrm{mx}mx 改成 xxx。
所有长度都是正整数，所以初始值可以取 000。这样第一根纸带读入后也能正常更新。全部读完时，mx\mathrm{mx}mx 就是所有纸带中的最大长度。题目只做比较，长度至多为 10910^9109，普通整数能够保存。
部分分说明：
* 测试点 1∼101\sim101∼10（全量数据，每点 101010 分）：依次读入并维护最大长度，使用完整的线性扫描算法；本题采用普通逐点计分。
实现步骤
1. 读入纸带根数 nnn，将 mx\mathrm{mx}mx 初始化为 000。
2. 依次读入每根纸带的长度 xxx。
3. 如果 x>mxx>\mathrm{mx}x>mx，令 mx=x\mathrm{mx}=xmx=x。
4. 全部读完后，输出 mx\mathrm{mx}mx。
正确性说明
读入第一根纸带前，mx=0\mathrm{mx}=0mx=0，小于所有合法长度。每次读入新长度时，程序保留原先已读长度的最大值与当前长度中较大的一个。因此，每轮结束后，mx\mathrm{mx}mx 都是当前所有已读纸带的最大长度。读完全部 nnn 根纸带后，它就是题目要求的答案。
复杂度分析
每根纸带只读入并比较一次，时间复杂度为 O(n)O(n)O(n)。只保存当前长度和最大长度，额外空间复杂度为 O(1)O(1)O(1)。
参考代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
C 三格合计
题意简述
第一行输入格子数量 nnn，第二行输入按原顺序排列的数值 a1,a2,…,ana_1,a_2,\ldots,a_na1 ,a2 ,…,an 。满足 3≤n≤1000003\le n\le1000003≤n≤100000，0≤ai≤1090\le a_i\le10^90≤ai ≤109。
选择恰好连续的三个格子，输出最大的三格合计，以及获得这个合计的最小起点编号。起点从 111 开始，格子保持原顺序，首尾不相接。
样例 #1 的数值为 2,5,4,1,6,02,5,4,1,6,02,5,4,1,6,0。四个合法起点的合计依次为 11,10,11,711,10,11,711,10,11,7。最大值是 111111，最早起点为 111，所以依次输出 111111 和 111。
解题思路
题意分析
一次选择由起点 iii 唯一确定，包含的位置是 i,i+1,i+2i,i+1,i+2i,i+1,i+2。为了让最后一个位置不超过 nnn，合法起点恰好是 1≤i≤n−21\le i\le n-21≤i≤n−2。
先读入数组，再从左到右枚举每个起点，直接计算三项和
sm=ai+ai+1+ai+2\mathrm{sm}=a_i+a_{i+1}+a_{i+2} sm=ai +ai+1 +ai+2
用 mx\mathrm{mx}mx 保存目前的最大合计，用 pos\mathrm{pos}pos 保存对应起点。只有 sm>mx\mathrm{sm}>\mathrm{mx}sm>mx 时才更新两个值。因为起点按从小到大的顺序检查，相等时保留旧记录，就保留了最早起点。
所有数值都不小于 000，所以将 mx\mathrm{mx}mx 初始化为 −1-1−1，第一次检查一定会更新。三个数的和最大为 3×1093\times10^93×109，超过常见 323232 位整数的上限，因此数组和求和变量使用 C++ 的 long long 类型。
部分分说明：
* 测试点 1∼201\sim201∼20（全量数据，每点 555 分）：枚举所有合法起点，计算三项和并维护最早最优起点；本题采用普通逐点计分，完整算法适用于全部测试点。
实现步骤
1. 读入 nnn 和数组，令 mx=−1\mathrm{mx}=-1mx=−1、pos=1\mathrm{pos}=1pos=1。
2. 依次枚举起点 i=1,2,…,n−2i=1,2,\ldots,n-2i=1,2,…,n−2。
3. 计算 sm=ai+ai+1+ai+2\mathrm{sm}=a_i+a_{i+1}+a_{i+2}sm=ai +ai+1 +ai+2 。
4. 如果 sm>mx\mathrm{sm}>\mathrm{mx}sm>mx，令 mx=sm\mathrm{mx}=\mathrm{sm}mx=sm、pos=i\mathrm{pos}=ipos=i；相等时保持原记录。
5. 依次输出 mx\mathrm{mx}mx 和 pos\mathrm{pos}pos。
正确性说明
每种合法选择都由最左边的起点唯一确定，且所有合法起点恰好是 1,2,…,n−21,2,\ldots,n-21,2,…,n−2。循环检查了这些起点，所以全部合法选择都被计算。
每检查一个起点，程序在原最大合计与当前合计之间保留较大的一个。因此循环结束时，mx\mathrm{mx}mx 就是所有合法选择中的最大合计。
循环按起点升序进行，只有合计严格变大才更新 pos\mathrm{pos}pos。遇到相同合计时，旧起点更早且被保留。因此最终 pos\mathrm{pos}pos 是获得最大合计的最小起点，两个输出都正确。
复杂度分析
读入 nnn 个数后检查 n−2n-2n−2 个起点，每个起点只做常数次运算，时间复杂度为 O(n)O(n)O(n)。保存整个数组，额外空间复杂度为 O(n)O(n)O(n)。
参考代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
D 接龙断点
题意简述
第一行输入单词数量 nnn，接下来 nnn 行依次输入单词。满足 1≤n≤10001\le n\le10001≤n≤1000，每个单词长度为 111 到 100100100，只包含小写英文字母。
从第 222 个单词开始，比较前一个单词的末字符与当前单词的首字符。输出第一个接龙失败的当前单词编号；全部成功时输出 000。
样例 #1 中，map、pen、nose、egg、goat 的相邻首尾字符依次相同，所以输出 000。样例 #2 中，bc 的末字符与 da 的首字符不同，第一次失败发生在第 333 个单词，所以输出 333。
解题思路
题意分析
用字符数组 pre\mathrm{pre}pre 保存前一个单词，用 cur\mathrm{cur}cur 读入当前单词。设前一个单词长度为 len\mathrm{len}len，它的末字符下标是 len−1\mathrm{len}-1len−1，当前单词首字符下标为 000。
将答案 ans\mathrm{ans}ans 初始化为 000。从编号 222 开始按顺序比较：当 ans=0\mathrm{ans}=0ans=0 且两个字符不同时，把当前编号记为答案。一旦记录了首次失败，后续比较保持答案不变。
每轮结束时，把当前单词复制到前一个单词的位置，供下一轮比较。长度为 111 的单词也按相同规则处理，因为此时首、末字符的下标都是 000。
部分分说明：
* 测试点 1∼201\sim201∼20（全量数据，每点 555 分）：按原顺序检查每对相邻单词并保留首次失败编号；本题采用普通逐点计分，完整算法适用于全部测试点。
实现步骤
1. 读入 nnn 和第一个单词，令 ans=0\mathrm{ans}=0ans=0。
2. 依次读入编号 i=2,3,…,ni=2,3,\ldots,ni=2,3,…,n 的当前单词。
3. 求出前一个单词的长度，比较前词末字符与当前首字符。
4. 如果本轮失败且 ans=0\mathrm{ans}=0ans=0，令 ans=i\mathrm{ans}=ians=i。
5. 用当前单词更新前一个单词；全部处理完后输出 ans\mathrm{ans}ans。
正确性说明
检查编号 iii 前，pre\mathrm{pre}pre 保存编号 i−1i-1i−1 的单词，cur\mathrm{cur}cur 读入编号 iii 的单词。因此本轮比较的正是题目要求的相邻首尾字符。检查后把当前单词复制给前一个单词，所以下一轮仍满足这一对应关系。
编号按升序检查，第一次字符不同时，记录的是最早失败的后一个单词编号。此后答案保持不变。若所有相邻单词都符合规则，答案始终为 000。因此输出符合题意。
复杂度分析
设所有单词的总长度为 LLL，最长单词长度为 WWW。每个单词只进行常数次读入、求长度与复制，时间复杂度为 O(L)O(L)O(L)。只保存两个单词，额外空间复杂度为 O(W)O(W)O(W)；本题 W≤100W\le100W≤100。
参考代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
E 竖直落珠
题意简述
盒子有 nnn 行 mmm 列，每格用 000 或 111 表示空格或珠子。所有珠子只在原列向下落，最后紧靠这一列的底部。
输入先给出 n,mn,mn,m，再给出整个表格；输出珠子停止后的 nnn 行 mmm 列表格。数据范围为 1≤n,m≤1001\le n,m\le1001≤n,m≤100。
样例一中，盒子有 444 行 333 列，每列都有 222 颗珠子。因此停止后前两行都是 000，后两行都是 111。
解题思路
题意分析
珠子只能在原列中移动，所以每一列的珠子数量始终不变。设第 jjj 列有 cntj\mathrm{cnt}_jcntj 颗珠子，那么停止后这一列最下面的 cntj\mathrm{cnt}_jcntj 个格子是 111，其余格子是 000。
共有 nnn 行，空格恰好占据前 n−cntjn-\mathrm{cnt}_jn−cntj 行。因此输出第 iii 行第 jjj 列时，若 i>n−cntji>n-\mathrm{cnt}_ji>n−cntj ，就输出 111；否则输出 000。读入表格时只需累加各列的珠子数量。
部分分说明：
* 测试点 1∼201\sim201∼20（全量数据）：本题按测试点计分，每点 555 分，共 100100100 分，未划分独立子任务。对所有测试点使用按列计数、从底部填充的完整算法。
实现步骤
1. 读入 n,mn,mn,m，将各列珠子数量初始化为 000。
2. 按行读入表格，把每个格子的值加到它所在列的计数中。
3. 依次输出每个格子：满足 i>n−cntji>n-\mathrm{cnt}_ji>n−cntj 时输出 111，否则输出 000。
4. 同一行的相邻数字之间输出一个空格，每行结束后换行。
正确性说明
第 jjj 列下落前后都有 cntj\mathrm{cnt}_jcntj 颗珠子。全部停止时，任一珠子下方都不能有空格，否则它还能继续下落。因此该列所有珠子必定紧靠底部，最终状态唯一：最后 cntj\mathrm{cnt}_jcntj 格为 111，前面的格子为 000。
程序统计的数量与原表格一致，并按这一唯一状态输出每列，所以整个输出表格正确。
复杂度分析
读入和输出各访问 nmnmnm 个格子，时间复杂度为 O(nm)O(nm)O(nm)。保存各列计数需要 O(m)O(m)O(m) 的额外空间。
参考代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
F 彩带对齐
题意简述
长彩带有 nnn 格，短彩带有 mmm 格。保持短彩带方向不变，将其完全放在长彩带上，覆盖位置颜色相同就得 111 分。
输入两条彩带的长度及各格颜色，输出最高分和达到最高分的不同起点数量。数据范围为 1≤m≤n≤3001\le m\le n\le3001≤m≤n≤300，颜色编号不超过 10910^9109。
样例一中，长彩带颜色依次为 1,2,1,2,1,31,2,1,2,1,31,2,1,2,1,3，短彩带为 1,2,11,2,11,2,1。从起点 111 或 333 放置都得到 333 分，其余起点得到 000 分，所以输出的最高分为 333，最优起点数量为 222。
解题思路
题意分析
短彩带必须完整落在长彩带内，所以合法起点为 1,2,…,n−m+11,2,\ldots,n-m+11,2,…,n−m+1。固定起点 sss 后，短彩带第 jjj 格覆盖长彩带第 s+j−1s+j-1s+j−1 格。依次比较这 mmm 对颜色，就能求出当前得分。
用 mx\mathrm{mx}mx 保存已检查摆放的最高分，用 cnt\mathrm{cnt}cnt 保存对应起点数量。如果当前得分更高，更新最高分，并把计数设为 111；如果得分相同，计数增加 111。
最高分初始设为 −1-1−1，而合法得分最小为 000，因此第一个起点一定能建立答案。即使所有摆放得分都是 000，也能统计全部最优起点。
部分分说明：
* 测试点 1∼201\sim201∼20（全量数据）：本题按测试点计分，每点 555 分，共 100100100 分，未划分独立子任务。对每个起点逐格比较颜色，使用完整枚举算法。
实现步骤
1. 读入两条彩带的长度和颜色数组。
2. 枚举起点 sss，范围从 111 到 n−m+1n-m+1n−m+1，包含两端。
3. 对当前起点，比较 as+j−1a_{s+j-1}as+j−1 与 bjb_jbj ，将同色的覆盖对数累加为本次得分。
4. 根据本次得分与最高分的大小关系，更新最高分和最优起点数量。
5. 输出最终的最高分和数量。
正确性说明
固定一个起点时，内层循环恰好检查全部 mmm 对覆盖方格，颜色相同才计分，因此得到的就是该次摆放的真实得分。
外层循环枚举所有合法起点。遇到更高分时，以前记录的起点不再最优，所以重新计数为 111；遇到同分时，当前起点恰好提供一个新最优摆放，所以增加计数。由此，每次检查后，保存的分数和数量都对应已检查起点中的最优结果。全部起点检查结束后，输出即为题目所求。
复杂度分析
共进行 (n−m+1)m(n-m+1)m(n−m+1)m 次颜色比较，时间复杂度为 O(nm)O(nm)O(nm)。保存两条彩带需要 O(n+m)O(n+m)O(n+m) 空间。
参考代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
G 最近刻度
题意简述
有 nnn 个独立的刻度牌，第 iii 个牌上的数为 aia_iai 。选择两个不同的刻度牌，求它们数值差的最小值，并统计达到最小差值的无序对数。
输入刻度牌数量及全部数值，输出最小差值和对应对数。相同数值的不同刻度牌仍是不同物品，每对只计一次。数据范围为 2≤n≤1000002\le n\le1000002≤n≤100000，0≤ai≤1090\le a_i\le10^90≤ai ≤109。
样例一中，数值 888 出现两次，组成 111 对；数值 333 出现三次，组成 333 对。最小差值是 000，达到这一差值的共有 444 对。
解题思路
题意分析
先将所有数从小到大排序，再分两种情况处理。
如果存在重复数，最小差值一定是 000。某个数出现 ccc 次，从中选两个不同刻度牌共有
c(c−1)2\frac{c(c-1)}{2} 2c(c−1)
种方法。分母中的 222 用于去掉同一对的两种先后顺序。遍历每段相同数值，把各段的贡献相加，就得到全部零差值对数。
如果所有数都不同，排序后任意不相邻两数的差，都是至少两个正的相邻差之和，因此严格大于其中的相邻差。于是最小差值只能出现在相邻位置。检查每一对相邻数，维护最小差及其出现次数即可。
对数最大为
100000×999992=4999950000,\frac{100000\times99999}{2}=4999950000, 2100000×99999 =4999950000,
超过常见 323232 位整数范围，因此对数及分组长度乘法使用 long long。数值和差值均不超过 10910^9109，可以使用 int。
部分分说明：
* 测试点 1∼201\sim201∼20（全量数据）：本题按测试点计分，每点 555 分，共 100100100 分，未划分独立子任务。使用排序后的分组计数与相邻差统计完整算法，兼顾重复值和大对数。
实现步骤
1. 读入全部数值，按从小到大的顺序排序。
2. 依次找到每个相同数值分组，按组长 ccc 累加 c(c−1)/2c(c-1)/2c(c−1)/2。
3. 若零差值对数大于 000，直接输出最小差值 000 和这个对数。
4. 否则遍历所有相邻差；出现更小差值时重设计数，出现相同最小差值时增加计数。
5. 输出保存的最小差值和对数。
正确性说明
若存在重复数，最小差值为 000。差值为 000 的一对刻度牌必定来自同一个相同值分组，每组恰好有 c(c−1)/2c(c-1)/2c(c−1)/2 对。不同分组的牌不会组成零差值对，故所有分组贡献之和就是答案。
若没有重复数，排序后的相邻差都为正。任何不相邻两数的差均严格大于某个相邻差，所以不可能达到全局最小差。程序检查全部相邻位置，并在发现更小差值时更新答案、相同差值时增加计数，因而得到全部最优对。
这两种情况覆盖所有输入，程序输出正确。
复杂度分析
排序需要 O(nlogn)O(n\log n)O(nlogn) 时间，其余扫描需要 O(n)O(n)O(n) 时间，总时间复杂度为 O(nlogn)O(n\log n)O(nlogn)。保存数组需要 O(n)O(n)O(n) 空间，排序额外调用栈为 O(logn)O(\log n)O(logn)。
参考代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
H 连续整数拼和
题意简述
给定正整数 NNN，选择至少两个连续正整数，使它们的和恰好为 NNN。首项不同或长度不同，都算不同方案。
输入一个 NNN，输出方案总数和所有方案中的最大长度；没有方案时两项均为 000。数据范围为 1≤N≤10121\le N\le10^{12}1≤N≤1012，首项必须至少为 111。
样例一中，15=7+8=4+5+6=1+2+3+4+515=7+8=4+5+6=1+2+3+4+515=7+8=4+5+6=1+2+3+4+5，共有 333 种方案，最长使用 555 个数，因此输出 333 和 555。
解题思路
题意分析
枚举连续整数列的长度 kkk。由于首项至少为 111，长度为 kkk 时，最小的和是 1+2+⋯+k1+2+\cdots+k1+2+⋯+k。把这一列正着、倒着各写一次，对应位置相加都等于 k+1k+1k+1，从而得到
1+2+⋯+k=k(k+1)2.1+2+\cdots+k=\frac{k(k+1)}{2}. 1+2+⋯+k=2k(k+1) .
因此，只需枚举满足 k≥2k\ge2k≥2 且 k(k+1)/2≤Nk(k+1)/2\le Nk(k+1)/2≤N 的长度。这样的长度最多约为 2N\sqrt{2N}2N ，在本题范围内可以逐个检查。
固定长度 kkk，设首项为 aaa。每个数都包含一个 aaa，额外增加的部分依次为 0,1,…,k−10,1,\ldots,k-10,1,…,k−1，所以
ka+k(k−1)2=N.ka+\frac{k(k-1)}{2}=N. ka+2k(k−1) =N.
令剩余量
rem=N−k(k−1)2.\mathrm{rem}=N-\frac{k(k-1)}{2}. rem=N−2k(k−1) .
若 rem\mathrm{rem}rem 能被 kkk 整除，就能得到唯一的整数首项 a=rem/ka=\mathrm{rem}/ka=rem/k。长度上界已经保证 N≥k(k+1)/2N\ge k(k+1)/2N≥k(k+1)/2，所以 rem≥k\mathrm{rem}\ge krem≥k，这个首项一定为正整数。
按长度递增枚举，每遇到一个合法长度就把方案数增加 111，并将最长长度更新为当前长度。输入和中间乘法均使用 long long，以容纳 101210^{12}1012 量级的数。
部分分说明：
* 测试点 1∼201\sim201∼20（全量数据）：本题按测试点计分，每点 555 分，共 100100100 分，未划分独立子任务。枚举所有满足长度上界的 kkk，用整除条件判断首项，使用完整算法。
实现步骤
1. 读入 NNN，将方案数和最长长度都初始化为 000。
2. 从 k=2k=2k=2 开始递增枚举，循环条件为 k(k+1)/2≤Nk(k+1)/2\le Nk(k+1)/2≤N。
3. 计算 rem=N−k(k−1)/2\mathrm{rem}=N-k(k-1)/2rem=N−k(k−1)/2，检查 rem mod k\mathrm{rem}\bmod kremmodk 是否为 000。
4. 若能够整除，将方案数增加 111，并将最长长度更新为 kkk。
5. 输出方案数和最长长度；没有合法长度时，两个初始值都会保留为 000。
正确性说明
任一合法方案的长度至少为 222，且它的和不小于 k(k+1)/2k(k+1)/2k(k+1)/2，因此其长度一定在循环枚举范围内。其首项满足求和式，所以对应剩余量一定是 kkk 的倍数，程序会将它计入。
每个被程序计入的长度都通过了整除检查，因此首项是整数；循环范围又保证首项至少为 111。按此首项写出的连续整数列，长度至少为 222，且求和恰好为 NNN，所以每次计入的方案都合法。
对于固定长度，求和式唯一确定首项，因此不同计数对应不同方案，且不会重复。程序按长度递增检查，最后记录的合法长度就是最大长度；无方案时保留 000。故两项输出均正确。
复杂度分析
最多检查约 2N\sqrt{2N}2N 个长度，每次检查只进行常数次算术运算。因此时间复杂度为 O(N)O(\sqrt{N})O(N )，额外空间复杂度为 O(1)O(1)O(1)。
参考代码
