简单的数学题（lv友问题？忘记学名了……免得大家某度或者某歌）

.·.·.

小明（Alice）希望横穿沙漠……然而小明发现横穿沙漠的他需要喝水&吃东西。于是小明决定，独自一人背负物资横穿沙漠，自己布置一整条资源的供应链。
已知小明横穿沙漠全程为a公里（unsigned int），小明能够承载的物资可以让小明行进b公里（unsigned int，大于0小于a），小明可以在任何一个整数公里处放下自己身上的物质，或者拿起那里原本具有的物资
问小明们横穿沙漠至少需要多少物资。
输入：若干行，每行两个整数，第一个是a，第二个是b。
输出：若干行，每行一个数，为小明横穿沙漠所需要的最少物资，直到遇到无论如何小明也不可能横穿沙漠的情况时输出0，并停止后续数据的计算。
输入样例：

4 3
4 2
56789 4321

输出样例：

6
0

试试看吧

三人行必有师焉

假设有m的物资，那么这m的物资每前进1公里，需要消耗【m/b】*2-1的储备。（【m/b】代指m/b要上取整，意思是每次可以带b的储备，那么所有储备都往前走1米需要搬的次数，而往返需要消耗2倍的次数，最后一次只需要前进，不需要回来，所以-1）那么剩余物资量是m-（【m/b】*2-1），此时令m=m-（【m/b】*2-1），至m=0则到达最远距离，此时m的递归次数就是a。同样，倒推回来，最后一段路程是每前进1公里，消耗1的物资储备，b-2b之间的路程，每前进1公里，消耗物资是3，2b-3b的路程每前进1公里消耗的物资是5，以此类推，a的路程可以划分为a/b个段，需要最少的物资是b+3b+...+（2*【a/b】-3）*b+(2*【a/b】-1)*(a-（【a/b】-1）*b)。这个式子非常容易递归。写的比较急，可能有疏忽，但思路是这样应该没错。

aristotllgood

背包问题吧 算法里面的

.·.·.

aristotllgood 发表于 2017-3-13 22:18
背包问题吧 算法里面的

好像不是……01背包是NPC……然而这个应该不是
记得题目不难……然而想做的话……
让我先想想……
至少我们需要递归
最简单的情况当a<=b，虽然题目不允许然而我们可以用这种方法来辅助思维
我们可以发现这种情况只需要一次就能走完，只需要消耗a的物资
然后，a=b+1一直到a=b+floor(b/3)，这个时候就需要2次……需要一次往返和a+(b-a)*3的物资
可是，为什么偏偏现在需要2次呢？
观察上文，我们发现了两个关键的时间点，一个是“往返”，因为题目可以看成，每往回走一步需要消耗2点资源，而一共消耗了a+2*（往回走的步数）这么多资源
当然，更多的，还是另一个时间点，就是，如果我们希望保证所有的资源存放处尽可能靠近开始位置（因为，越靠近终点，放置资源的代价就越大）
而这时候，我们就会发现，哪怕是最优情况也存在一种可能使得所有的资源存放处尽可能靠近开始位置——或者说，在距离重点还有b公里的位置，一定有一个时刻，小明手中的资源恰好为b
剩下的容我&大家再想想

midpoint

这不是动态规划吗？

.·.·.

midpoint 发表于 2017-3-14 08:56
这不是动态规划吗？

好像是递归

.·.·.

三人行必有师焉 发表于 2017-3-14 00:29
假设有m的物资，那么这m的物资每前进1公里，需要消耗【m/b】*2-1的储备。（【m/b】代指m/b要上取整，意思是 ...

睡了一觉，起来上课……课上刚想起来这个方法合理性的证明，准备回来把欧拉一笔画问题贴上来……然后答案就来了呢

这个解法的确是合理的……因为任何一种条路径，考虑小明从i公里处到i+1公里处往返的次数，记为k_i
则我们可以找到一条消耗相同的路径，满足
首先小明从第0公里到第1公里处往返k_0次，并从第0公里处带走了所需要的全部物资
然后小明从第1公里到第2公里处往返k_1次，并从第1公里处带走了所需要的全部物资
……
直到小明到达终点
因而我们可以最小化k_0...k_a来保证小明消耗的物资最少

话说……有没考虑过连续的情形呢表示可能要用微积分……算出来一个带ln（物资能走多远）或者指数（走到给定路程需要多少物资）的东西

三人行必有师焉

.·.·. 发表于 2017-3-14 13:02
睡了一觉，起来上课……课上刚想起来这个方法合理性的证明，准备回来把欧拉一笔画问题贴上来 ...

没想出需要微积分的情况，因为每前进1km也好，1m也好，甚至1cm也好，都可以用这个思路解决，即只要前进距离在0-b之间，前进1个单位的距离消耗的物资就是1*（1个单位度量消耗的物资=1km消耗物资/1km换算成该单位度量的份数），举个例子说，如果1km需要1kg物资，那么如果需要的单位度量是1m，则可以用1kg/1000m=1g/m，那么每前进1个单位消耗物资就是1g/m。b-2b之间消耗物资是3g/m*该段前进距离，2b-3b之间消耗的物资是5g/m*该段前进的距离，以此类推。所以只要根据需要把这个距离轴拉伸，不断细化这个距离度量单位，单位再小也能够计算出一个值。微积分不就是把度量不断细化，最后变成连续么。那可以把每前进一公里细化到每前进1cm，这样的细化应该足够了。

.·.·.

三人行必有师焉 发表于 2017-3-15 17:40
没想出需要微积分的情况，因为每前进1km也好，1m也好，甚至1cm也好，都可以用这个思路解决，即只要前进距 ...

然而这样逼近离微积分很接近了啊
其实……我们在计算一个类似(1+1/n)^n的数值……这个是e……然后别的都可以用这个转化成连续的
话说连续会简单很多……因为积分相当于提前算了很多东西，效率总会比递归高一些