本来应该今天笔试的，但....起来就比较晚了，早上我的头脑也不大清醒，就干脆直接顺延吧，然后看到了这里给出的题目：
https://www.nowcoder.com/discuss/461872
1.给 n 个恐龙蛋及恐龙蛋的大小，按从大到小排列，第 i 个恐龙蛋每天增大 i，问最少几天会出现两个同样大小的恐龙蛋。
2.n 个客栈依次排列，给出 n - 1 条路的权重。从任意一处出发，每走过一条路，该路的权重减 1，但得到 1 点利益。不能走权重为 0 的路。求最大利益。
看到之后想思路就想了好久，估计让我写就只能写出一道吧，先记录下我的思路，顺便等一下有没有大佬可以指点下我有更好的思路。
1.一开始想直接暴力，但感觉就算暴力写起来也是有点麻烦的。就一点点分析下，假设i-1位置有a个，i位置有b个，i+1位置有c个，那三个中两两组合的话，则天数是a-b,b-c,(a-c)/2，那可以看出来了(a-c)/2显然不是，他是另两个的平均数所以肯定是相邻两个位置会先达到相等，也就相当于求相邻差最小的。其实扩展一下想的话i位置有i位置有a个，j位置有b个，k位置有c个，天数就是(a-b)/(j-i)，(b-c)/(k-j)，(a-c)/(k-i)，那么如果要(a-c)/(k-i)最小，那建立两个不等式之后其实是要满足(a-b)k+(b-c)>(a-c)j，(a-b)k+(b-c)<(a-c)j完全矛盾，所以结论就是两个距离远的位置一定不是所求，至少会有距离近的比他好，所以这个天数一定诞生于相邻的位置理论上应该没问题，不知道实际上能不能通过。
2.客栈的话我一开始想的就是不断的递归迭代，但肯定会溢出......我的思路是假设我单方向往右走不回来，那我应该每个都把它耗尽再走，或者就留一个，也就是取路径上最大的奇数假设是right_max。但如果是还回来的话，应该是次大的奇数吧，然后回来的路上再加个路径长就假设是right_submax吧，然后再取到左侧不回头的left_max和左侧回头的left_submax，然后从不同位置出发就组合right_max和left_submax对比right_submax和left_max得到最大的应该就是这个位置出发的最大利益了吧....再比较每个位置上的值取个最大。。。。。感觉纰漏很大但我也不知道该怎么完善了，有大佬可以指导一下吗
全部评论
(4) 回帖