计算第9天结束时剩余的金额。
给定a，b和n，其中1美元是每天获得的钱，b是要购买的食物的成本，n是每天的数目。
每一天"a“钱都贷到你的账户上，你想尽可能多地用可用的钱购买食物，如果你已经有了食物，那么你就不会买day.you重复这一任务n天的食物，并且想要计算n天结束时剩下的钱。
蛮力解决方案是模拟任务，但这将无法工作，因为天数非常高，如10**9。
我想到的另一种方法
- 如果是a==b，那么答案是0
- 如果b>a回答为(a*n)%b
当a< b时，我很难找到这个案子的答案。
下面是一个例子
a=5，b=3，n=3 第一天:5块钱我们最多可以买一份食物，剩下的两块钱。 第二天:第二天(前一天)+5美元，我们最多可以买2块食物，1美元剩余 第三天:1(前一天)+5美元我们不会购买任何东西，因为我们已经有了一种食物(从前一天开始) 6美元在第3天结束时
回答 1
Stack Overflow用户
发布于 2016-04-22 15:12:26
我可能弄错了，但你每次买的天数都会成倍增长。如果你今天有钱买x食物，下次你会有x*(a/b)，下一次你会有x*(a/b)*(a/b)等等。
所以如果你利用指数增长的话，你应该能够强迫它。
如果今天你有0的食物和x的钱，那么你可以买x/b的食物，所以你可以跳过x/b的日子(当你又有了0的时候)，你下次会有(x%b) + (x/b)*a钱。由于您遵循指数增长，您的复杂性将是O(logN)。如果还不清楚，请使用a=2, b=1并看到您很快就可以获得大量的数据，并且您可以轻松地跳过很多天。
有一点要注意的是，指数值的启动速度可能会很慢。如果a和b非常接近(a=1000000 b=999999)，那么a/b将非常接近于1。尽管如此，logN，但您在慢周期中花费的时间太多。在实践中，这意味着您将执行许多迭代，其中您只需跳过一两天。你也可以缩短这一点，注意你每个周期赚多少钱(在我的例子中，你必须在两天内购买食物，在我的例子中是1)，并计算出你需要多少周期才能多买1单位的食物(你需要知道在这个周期之后剩下的东西，把它加到你现在的钱中，除以食物的成本)。一旦你知道这一点，你可以跳过所有的周期，直到你可以买更多的食物。
https://stackoverflow.com/questions/36787606
复制相似问题
腾讯云开发者
