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$

全部评论

推荐最新楼层

04-08 22:18

西安电子科技大学 C++

美团聊天一面光速二面

uu们，有没有人知道团子什么情况啊，一面过程中面试官全聊项目，也不深挖，就问难点是什么，负责什么部分，介绍项目，两道手撕题就结束了，总共40min。以为就kpi面试，结果光速二面。。。。什么情况

pixel1：大佬啊，这么猛，这种情况应该是稳了

美团二面1957人在聊美团求职进展汇总

点赞评论收藏

04-09 08:05

中国人民大学嵌入式软件开发

不是这么离谱吗？一个项目40块？

我看标题以为40W,我觉得最差也得40k,点进去一看40块。你永远想不到客户的预算有多低... 要求“前端使用vue+element开发一个pc端宠物网站和vue+vant开发一个移动端网站，类型是宠物网站的。客户预算40” 全网最受欢迎的嵌入式面经面经一共32篇文章，12w+字数，包含全部最新的面试必问考点，4.7w+同学学习，2800+订阅，非常适合在找工作面经薄弱的同学，3000+订阅还会涨价，提前订阅提前享受，持续更新中。原帖链接：https://www.nowcoder.com/creation/manager/columnDetail/MJNwoMc

野猪不是猪🐗：哎呀，看来这位客户预算确实挺让人意外的呢！不过，别灰心，有时候客户的预算有限，但项目完成后说不定能带来意想不到的收获呢！😊 至于你提到的嵌入式面经，听起来好像很棒的样子！如果你对求职有帮助，那确实值得订阅学习哦！悄悄告诉你，点击我的头像，我们可以私信聊聊更多求职经验和技巧哦～🎉 对了，你对Vue和Element/Vant的开发有什么疑问或者想要分享的经验吗？我们可以一起探讨一下～😉

牛客在线求职答疑中心通信硬件2024笔试面试经验

点赞评论收藏