3 solutions
-
0
题面描述:
某公司为新用户推出大礼包,用户从任意一天注册后,可以连续登录天并领取金币。金币数量与一年中个月的日历相关,每个月第一天得1个金币,第二天得2个金币,以此类推。输入包含月数和连续登录天数,以及每个月的天数。要求计算用户在注册后连续登录天,最多可以获得的金币总数,且连续登录可能跨年。
题解
塔子哥希望找到连续
x
天内可以获得最多金币的方案。为了实现这一目标,我们的日历数据是一个长度为n
的数组d
,其中每个元素表示每个月的天数。由于塔子哥可以跨越到下一年的第一个月,因此我们需要考虑跨年情况。为了解决这个问题,我们采用了以下思路:-
双倍日历数组:将日历数组
d
复制一份,形成一个长度为2n
的数组。这一做法确保我们可以在任何地方找到长度为x
的连续天数,并且能够平滑地处理跨年情况。 -
滑动窗口算法:我们通过滑动窗口的方式来计算在不同起点下,连续
x
天可以获得的金币总数。窗口的初始位置从0
开始,每次移动一格,尝试不同的起点。 -
动态调整窗口:在窗口滑动过程中,维护当前窗口中的天数和金币总和。如果当前窗口内的天数和大于
x
,则从左侧移除天数,直到窗口中的天数和小于等于x
。 -
计算金币总数:当窗口天数和恰好等于
x
时,直接记录当前金币总和;如果小于x
,则计算剩余天数并用sumup()
方法加上右侧不足的金币数。 -
更新最优解:每次计算得到的总金币数与当前的最优解比较,保留最大值。
代码解释
-
get(int n)
函数:计算从 1 到n
的金币数量,这里使用了高效的数学公式。 -
主函数逻辑:
- 输入
n
和x
,以及每个月的天数,并创建一个长度为2n
的数组。 - 使用滑动窗口遍历双倍数组,每次更新当前窗口的天数和金币总数。
- 通过动态调整窗口的左侧,确保总天数不超过
x
。 - 计算当前窗口的金币总数,并实时更新最大金币数量
res
。
- 输入
时间复杂度
该算法的时间复杂度为 (O(n)),每个元素最多被访问两次,因此可以在线性时间内找到答案。
代码实现
C++代码
Python代码
Java代码
代码注释说明
- 滑动窗口和范围控制:窗口控制中,
dayCnt
记录窗口中连续天数之和,若超过x
天,则缩小左边界。 - 金币计算:每个元素
d[i]
对应的金币数为连续整数的和,可以通过公式d[i] * (1 + d[i]) / 2
计算。 - 剩余天数计算:若窗口天数和小于
x
,则调用sumup()
计算剩余金币,以补全连续天数,使总天数等于x
。 - 最终输出:输出记录的最大金币数。
-
- 1
Information
- ID
- 78
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 4
- Tags
- # Submissions
- 602
- Accepted
- 61
- Uploaded By