2024-10-11 02:30 华南理工大学算法工程师发布于江苏

关注

A 题决策单调性证明

最小执行次数 $f(n)$ 可以表示为：

\begin{equation} f(n)= \left\{ \begin{aligned} n+\min_{1\leq i<n} \{ f(i)+f(n-1-i)\}, &&n>1\\ 0, && n=1 \end{aligned} \right. \end{equation}

证明： $f(n)$ 在 $i=2\lfloor \frac{n+3}{4}\rfloor-1$ 时取到最小值。

解析解

首先，打开 oeis，输入前几项 "0, 2, 3, 6, 8"，得到对应数列 A097383

发现有个解析解 $f(n) = (n+1)m-2^m-\lfloor\frac{n-1}{2}\rfloor$

其中 $m$ 为 $n$ 的二进制长度，即 $m=\lfloor log_2n+1\rfloor$

这个式子怎么来的不做详细叙述，只讨论一下 $f(n)=n+\min_{1\leq i<n} \{ f(i)+f(n-1-i)\}$ 取最小值的位置

凸函数

思路： $f(n)$ 不是凸函数，但是这个式子看起来和凸函数能搭上关系。为了用上凸函数的性质，思路是找到一个和 $f$ 极其接近的凸函数，并对二者的差进行讨论。

令 $g(n)=(n+1)m-2^m-\frac{n-1}{2}$ ，容易看出 $f(n)=g(n)+\frac{1}{2}[2 \ |\ n]$ 成立

引理1. $g(n)$ 是一个凸函数

证：

令 $m=\lfloor log_2n+1\rfloor$

当 $n+1$ 不为 2 的幂次时，那么 $\lfloor log_2(n+1)+1\rfloor=\lfloor log_2n+1\rfloor=m$ ，有 $g(n+1)-g(n)=m-\frac{1}{2}$

当 $n+1$ 为 2 的幂次时，那么 $\lfloor log_2(n+1)+1\rfloor=m+1$ ，即 $2^{m}=n+1$ ，有 $g(n+1)-g(n)=n+m+2-2^m-\frac{1}{2}=m+\frac{1}{2}$

因此， $g(n+1)-g(n)$ 单调不减， $g(n)$ 是一个凸函数

引理2. 对于一个凸函数， $g$ 满足：

\min_{1\leq i <n}\{ g(i)+g(n-1-i) \}=g(\lfloor \frac{n-1}{2} \rfloor)+g(\lceil \frac{n-1}{2} \rceil)

证：

当 $1\leq i\leq\lfloor\frac{n-1}{2}\rfloor$ 时， $g(i)-g(i-1)\leq g(n-i)-g(n-1-i)$ ，即 $g(i)+g(n-1-i)\leq g(i-1)+g(n-i)$ ，所以 $i$ 越靠近中间越小。

对 n 进行分类讨论，联系 $f$ 和 $g$

回顾一下 $f(n)=g(n)+\frac{1}{2}[2 \ |\ n]$ ，也就是 $n$ 为偶数时 $f(n)=g(n)+\frac{1}{2}$ ， $n$ 为奇数时 $f(n)=g(n)$

① $n$ 为偶数

因为 $\lfloor \frac{n-1}{2} \rfloor$ 和 $\lceil \frac{n-1}{2} \rceil$ 一定是一奇一偶，那么有

f(\lfloor \frac{n-1}{2} \rfloor)+f(\lceil \frac{n-1}{2} \rceil) = g(\lfloor \frac{n-1}{2} \rfloor)+g(\lceil \frac{n-1}{2} \rceil)+\frac{1}{2}

因为 $i$ 和 $n-1-i$ 也一定是一奇一偶，那么有

\begin{equation} \begin{aligned} f(n)=\min_{1\leq i<n} \{ f(i)+f(n-1-i)\} & = \min_{1\leq i<n} \{ g(i)+g(n-1-i)+\frac{1}{2}\} \\ & =g(\lfloor \frac{n-1}{2} \rfloor)+g(\lceil \frac{n-1}{2} \rceil)+\frac{1}{2} \\ & =f(\lfloor \frac{n-1}{2} \rfloor)+f(\lceil \frac{n-1}{2} \rceil) \\ \end{aligned} \end{equation}

所以 $n$ 为偶数时， $f(n)$ 在 $i=\lfloor\frac{n-1}{2}\rfloor$ 取到最小值

② $n \equiv 3 \mod 4$

此时 $\frac{n-1}{2}$ 为奇数，那么有

f(\lfloor \frac{n-1}{2} \rfloor)+f(\lceil \frac{n-1}{2} \rceil) = g(\lfloor \frac{n-1}{2} \rfloor)+g(\lceil \frac{n-1}{2} \rceil)

而 $f(n)\geq g(n)$ ，因此

\min_{1\leq i<n} \{ f(i)+f(n-1-i)\}\geq \min_{1\leq i<n} \{ g(i)+g(n-1-i)\}=f(\lfloor \frac{n-1}{2} \rfloor)+f(\lceil \frac{n-1}{2} \rceil)

而根据定义，有

\min_{1\leq i<n} \{ f(i)+f(n-1-i)\}\leq f(\lfloor \frac{n-1}{2} \rfloor)+f(\lceil \frac{n-1}{2} \rceil)

所以有

\min_{1\leq i<n} \{ f(i)+f(n-1-i)\} = f(\lfloor \frac{n-1}{2} \rfloor)+f(\lceil \frac{n-1}{2} \rceil)

所以 $n \equiv 3 \mod 4$ 时， $f(n)$ 在 $i=\lfloor\frac{n-1}{2}\rfloor$ 取到最小值

③ $n \equiv 1 \mod 4$

这是唯一特殊的情况，分成 $i=\frac{n-1}{2}$ , $i=\frac{n-1}{2}-1$ , $i<\frac{n-1}{2}$ 三种讨论。

令 $n=4p+1$

$(1)\ i=\frac{n-1}{2}$ ，即 $i=2p$

那么有 $f(i)+f(n-i-1)=f(2p)+f(2p)=2g(2p)+1$

$(2)\ i=\frac{n-1}{2}-1$ ，即 $i=2p-1$

那么有 $f(i)+f(n-i-1)=f(2p-1)+f(2p+1)=g(2p-1)+g(2p+1)$

根据 $g$ 的定义和之前的推论，有 $g(2p+1)-g(2p)=m-\frac{1}{2},\ g(2p)-g(2p-1)=m-\frac{1}{2}$ ，其中 $m=\lfloor log_2 2p \rfloor+1$

两式相减，有 $g(2p+1)+g(2p-1)=2g(2p)$

所以 $f(2p-1)+f(2p+1)<2f(2p)$ （换句话说，这时候取中点也就是 $\lfloor\frac{n-1}{2}\rfloor$ 不是最优的）

$(3)\ i<\frac{n-1}{2}-1$ ，即 $i<2p-1$

那么有

f(i)+f(n-i-1)\geq g(i)+g(n-i-1) \geq g(2p-1)+g(2p+1)=f(2p-1)+f(2p+1)

不可能更优

总结一下，即

\min_{1\leq i<n} \{ f(i)+f(n-1-i)\} = f(\lfloor \frac{n-1}{2} \rfloor)+f(\lceil \frac{n-1}{2} \rceil)-1=f(\lfloor \frac{n-1}{2} \rfloor-1)+f(\lceil \frac{n-1}{2} \rceil+1)

所以 $n \equiv 1 \mod 4$ 时， $f(n)$ 在 $i=\lfloor\frac{n-1}{2}\rfloor-1$ 取到最小值

结论

综上所述，对于 $f(n)=n+\min_{1\leq i<n} \{ f(i)+f(n-1-i)\}$ ，

$n\equiv 1 \mod 4$ 时， $f(n)$ 在 $i=\lfloor\frac{n-1}{2}\rfloor-1$ 取到最小值

$n \equiv 0,\ 2,\ 3 \mod 4$ 时， $f(n)$ 在 $i=\lfloor\frac{n-1}{2}\rfloor$ 取到最小值

把对称性考虑上，再合并这两种情况就是 $i=2\lfloor \frac{n+3}{4}\rfloor-1$

全部评论

推荐最新楼层

05-26 17:17

门头沟学院嵌入式软件工程师

vivo 暑期实习面经｜嵌入式方向

最近我整理了 vivo 暑期实习（嵌入式 / Linux 方向）的面经，发出来给后面要面的同学做个参考。技术面难度还是有的，节奏偏快，会顺着你的回答往下挖；整体氛围还行，但有几道题一旦答浅了就会立刻追问细节。面试题目进程和线程在内核里分别对应什么数据结构？创建线程和创建进程在内核路径上有什么异同？CFS 调度器里 vruntime 是什么？为什么用红黑树？新进程加入时如何防止老进程被饿死？nice 值、SCHED_FIFO / SCHED_RR 和 CFS 的关系是什么？实时调度会不会饿死普通进程？虚拟地址到物理地址的完整路径（MMU、页表、TLB）讲一遍；TLB miss 时会发生什么？伙伴...

点赞评论收藏

分享

05-25 11:50

华为OD机考考点揭秘｜题型分布 + 高频考点 + 必刷方向

备考机考正在刷题的小伙伴看过了！与完毕给大家整理了一份OD 机考完整考点体系，从题型分值、一星基础考点到二星重难点全覆盖，备考直接照着啃考点刷题就行，不走弯路！一、机考基础规则先理清考题配置：3 道编程题，分值 100、100、200，满分 400 分，150 分即可通关考试时长：150 分钟，不用每题跑满所有测试用例，凑够分数就行难度分布：2 道一星基础题 + 1 道二星难题，时间合理分配，三题尽量都提交，轻松凑分过线评分规则：按测试用例通过率给分，代码不完全 AC 也能拿部分分数，没时间写完写思路框架也能得分二、一星题必考高频考点（基础拿分核心）一星题是保底关键，难度低、题型固定，拿下就能...

点赞评论收藏

分享

04-15 18:11

中国人民大学前端开发其它

面试官角度谈谈还要刷力扣吗

上周组里招人，我面了六个候选人，回来跟同事吃饭的时候聊起一个让我挺感慨的现象。前三个候选人，算法题写得都不错。第一道二分查找，五分钟之内给出解法，边界条件也处理得干净。第二道动态规划，状态转移方程写对了，空间复杂度也优化了一版。我翻他们的简历，力扣刷题量都在300以上。后三个呢，就有点参差不齐了。有的边界条件没处理好，有的直接说这道题没刷过能不能换个思路讲讲。其中有一个女生，我印象特别深——她拿到题之后没有马上写，而是先问我：“面试官，我能先跟你确认一下我对题目的理解吗？”然后她把自己的思路讲了一遍，虽然最后代码写得不是最优解，但整个沟通过程非常顺畅。这个女生的代码不是最优的，但当我问她“如果这里是线上环境，你会怎么设计’的时候，她给我讲了一套完整的方案——异常怎么处理、日志怎么打、怎么平滑发布。她对这是之前在实习的时候踩过的坑。”我在想LeetCode到底在筛选什么？我自己的经历可能有点代表性。我当年校招的时候，也是刷了三百多道题才敢去面试。那时候大家都刷，你不刷就过不了笔试关。后来工作了，前三年基本没再打开过力扣。真正干活的时候，没人让你写反转链表，也没人让你手撕红黑树。更多的是：这个接口为什么慢了、那个服务为什么OOM了、线上数据对不上了得排查一下。所以后来我当面试官，慢慢调整了自己的评判标准。算法题我还会出，但目的变了。我出算法题，不是想看你能不能背出最优解。而是想看你拿到一个陌生问题的时候，是怎么思考的。你会先理清题意吗？你会主动问边界条件吗？你想不出来的时候会怎么办？你写出来的代码，变量命名乱不乱、结构清不清楚？这些才是工作中真正用得到的能力。LeetCode是一个工具，不是目的。它帮你熟悉数据结构和常见算法思路，这没问题。但如果你刷了三百道题，却说不清楚自己的项目解决了什么问题、遇到了什么困难、你是怎么解决的，那这三百道题可能真的白刷了。所以还要不要刷LeetCode？要刷，但别只刷题。刷题的时候，多问自己几个为什么：为什么用这个数据结构？为什么这个解法比那个好？如果换个条件，解法还成立吗？把刷题当成锻炼思维的方式，而不是背答案的任务。毕竟面试官想看到的，从来不是一台背题机器，而是一个能解决问题的人。

牛客51274894...：意思是光刷力扣还不够卷

AI时代还有必要刷lee...

点赞评论收藏

分享

04-03 10:26

中国矿业大学 Java

hr先为昨天的delay道歉了，态度很温柔也很专业。主要问一些压力的克服实习内容与成长，困难怎么克服到岗时间与实习时长为什么不考研先打了个mentor和leader比较忙的预防针反问：工作节奏，offer时间

二十岁的编程男神王大...：兄弟，到岗时间你说的多少呀，我们导师只能要求六月走，感觉说六月会不会给挂了offer

查看4道真题和解析

点赞评论收藏

分享

05-26 22:01

字节跳动_研发工程师

面试官：说一下 Agent 的常见范式

很多人一听到这个问题，就开始罗列一堆技术名词：ReAct、Plan-and-Executor、Reflection、Multi-Agent…如果面试官继续追问：为什么会出现这些范式？各自解决什么？本质区别在哪？项目里怎么选？很多人可能就会卡壳了。这些范式实际上都在解决一个问题：当任务越来越复杂时，如何让 Agent 变得更可靠？随着任务从简单的单工具调用，发展到多步骤长任务、跨领域复杂任务，再到企业级生产任务，Agent 暴露出一系列问题：长任务容易失控偏离目标、输出质量不稳定、单 Agent 上下文窗口有限、生产环境缺乏可控性与合规性等等。不同范式针对不同阶段的核心痛点提出了解决方案，但同时...

点赞评论收藏

分享

评论

5

收藏

全站热榜

更多

创作者周榜

更多

正在热议

更多

# 实习生的蛐蛐区 #

1007448次浏览 5133人参与

# 扒一扒那些奇葩实习经历 #

160659次浏览 1182人参与

# 发面经攒人品 #

8901000次浏览 98751人参与

# 应届生第一份工资要多少合适 #

28227次浏览 107人参与

# 27届实习投递记录 #

166347次浏览 1680人参与

# 应届生，你找到工作了吗 #

180936次浏览 914人参与

# 招聘要求与实际实习内容不符怎么办 #

226784次浏览 1077人参与

# 机械人值得去的小众企业 #

38375次浏览 68人参与

# 现在入门AI首先要做什么？ #

18304次浏览 145人参与

# 互联网行业现在还值得去吗 #

65692次浏览 380人参与

# 实习最想跑路的瞬间 #

147653次浏览 787人参与

# 面试反问你会问什么 #

213567次浏览 1962人参与

# 机械人，秋招第一次笔试的企业是哪家？ #

106946次浏览 715人参与

# 万物皆可发面经 #

5561次浏览 67人参与

# AI了，我在打一种很新的工 #

211511次浏览 2340人参与

# 实习，不懂就问 #

231700次浏览 1771人参与

# 实习教会我的事 #

82240次浏览 521人参与

# 网易求职进展汇总 #

218793次浏览 1542人参与

# 春招前还要继续实习吗？ #

72095次浏览 353人参与

# 校招求职有谈薪空间吗 #

234448次浏览 2400人参与

牛客网
牛客网在线编程
牛客网题解
牛客企业服务