算法笔试-编程练习-好题-06
【题目类型：滑动窗口、贪心、双指针、等差数列求和】
题目描述
某公司日对新用户推出大礼包，从任意一天注册开始，连续登录x天，每天可以领取一定的金币，领取金币的数量与该公司新设计的虚假世界的日历相关，该日历一年有n个月，第i个月有di天，每一年都一样。在每个月第一天会得到1个金币，第天会得到2个金币币第三天会得到3个金币，后面次类推。 请计算新用户注册后连续登陆x天，最多可以获取多少金币。 请注意，连续登陆可能会跨年。
解答要求 时间限制:C/C++ 500ms,其他语言:1000ms
内存限制:C/C++ 256MB, 其他语言:512MB
输入
第一行包含两个整数n和x(1≤n≤2∗10^5)，分别表示一年中的月数和连续登陆的天数。第二行包含 nn 个整数 d1,d2,...,dn，di表示第i个月的天数(1≤di≤10^6) 用例保证，1≤x≤d1+d2+...+dn
输出
打印新用户连续号陆x天最多可以获取的金币数量
样例1
输入
3 2
1 3 1
输出
5
样例3
输入
5 6
4 2 3 1 3
输出
15
解释
一年中每天获取的金币数是{1,2,3,4,1,2,1,2,3,1,1,2,3}(对应每个月中的天数)。如果在一年中的第12天开始注册登陆，最多可以获取2+3+1+2+3+4=15个金币
题目分析
【题目类型：滑动窗口、贪心、双指针、等差数列求和】
首先这题是个较为明确的滑动窗口类题目，我们只需要遍历每种情况即可获得最多的金币数。
获取金币的最小单位是天，但是如果以天为单位步长进行滑动窗口一定会超时的。我们仔细分析可以发现以月份为滑动窗口进行遍历，对每一种取值存在贪心的计算方式。
既然是滑动窗口类的题目，肯定可以使用双指针完成对滑动窗口的描述。我们以每个月为单位进行滑动，当窗口内的天数 大于等于 目标签到天数x时，我们应该计算该窗口内的最大金币数。
由于我们是固定窗口左侧，逐步扩大窗口右侧，因此当前窗口一定是左侧不变的情况下能容纳x的最小窗口。因此当窗口长度大于x时，一定是去除窗口左侧的日子，才能获得最多的金币。【这里比较难想，可以写几个例子分析一下】
对于可以跨年的问题，我们将明年的日历接到今年的日历后面即可。
因此总体思路就是：固定窗口左侧，扩大右侧直到可以包住x，此时贪心求金币数。然后向右移动窗口左侧直到无法包住x，再重新循环。
代码：
n, x = map(int, input().split())
month_days = list(map(int, input().split()))
month_jinbi = [ ((d+1)*d)//2 for d in month_days]month_days += month_days
month_jinbi += month_jinbiDayLength = 0
sum_all = 0
result = 0idx = 0 # 左指针
jdx = -1 # 右指针
while jdx < len(month_days)-1:jdx += 1DayLength += month_days[jdx]sum_all += month_jinbi[jdx]if DayLength >= x:while DayLength >= x:DayLength -= month_days[idx]sum_all -= month_jinbi[idx]idx += 1temp_moreDays = DayLength + month_days[idx-1] - xtemp_re = sum_all + month_jinbi[idx-1] - (((temp_moreDays+1)*temp_moreDays)//2)result = max(result, temp_re)print(result)