算法笔试-编程练习-好题-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_jinbi

DayLength = 0
sum_all = 0
result = 0

idx = 0     # 左指针
jdx = -1    # 右指针
while jdx < len(month_days)-1:
    jdx += 1
    DayLength += month_days[jdx]
    sum_all += month_jinbi[jdx]
    
    if DayLength >= x:
        while DayLength >= x:
            DayLength -= month_days[idx]
            sum_all -= month_jinbi[idx]
            idx += 1
        
        temp_moreDays = DayLength + month_days[idx-1] - x
        temp_re = sum_all + month_jinbi[idx-1] - (((temp_moreDays+1)*temp_moreDays)//2)
        result = max(result, temp_re)

print(result)