大礼包 - 华为机试真题题解

本文主要是介绍大礼包 - 华为机试真题题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

考试平台：时习知

分值： 200分（第二题）

考试时间： 2024-01-31 （两小时）

alt

题目描述

某公司针对新用户推出大礼包，从任意一天注册开始，连续登陆 x 天，每天可以领取一定的金币。

领取金币的数量与该公司新设计的虚拟世界的日历相关，该日历一年有 n 个月，第 i 个月有 $d_i$ 天，每一年都一样。

在每个月第一天会得到1个金币，第二天会得到 2个金币，第三天会得到 3 个金币…，后面依次类推。

请计算新用户注册后连续登陆 x 天，最多可以获取多少金币。

输入

第一行包含两个整数 n和 x ($1 \le n \le 2 * 10^5 $)，分别表示一年中的月数和连续登陆的天数。

第二行包含n 个整数 $d_l,d_2,...,d_n$ 、 $di $ 表示第 i 个月的天数 ( $\le d_i \le 10^6$ )。

用例保证， $\le x \le d_1 + d_2 + ... + d_n$ 。

输出

打印新用户连续登陆x天最多可以获取的金币数量。

示例1

输入：
3 2
1 3 2输出：
5解释： 
一年中每天获取的金币数是{1,1,2,3,1} (对应每个月中的天数)。如果在一年中的第3天开始注册登陆，最多可以获取 2+3=5个金币。

示例2

输入：
3 6
3 3 3输出：
12解释： 
一年中每天获取的金币数是{1,2,3,1,2,3,1,2,3} (对应每个月中的天数)。如果在一年中的第3天开始注册登陆，最多可以获取3+1+2+3+1十2=12 个金币。

示例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个金币。

Python 题解

该题使用滑动窗口求解。

解题思路：

由于题目中有一年的日历，考虑将月份 * 2 进行处理，相当于一个环，方便处理从年底再往后走的情况。
使用两个指针，left_idx 和 right_idx 分别表示左边界和右边界，left_num 和 right_num 分别表示左边界和右边界当前所在月份的天数。
首先，扩大窗口到 x，即计算连续登陆 x 天所能获取的金币数。
然后，保持窗口大小，尝试将最大金币数记录下来。通过不断右移左右指针，计算窗口内的金币数，同时记录最大金币数。
最后返回最大金币数。

Python 题解

from typing import Listdef solve(n: int, x: int, d: List[int]) -> int:coin_sum = 0  # 当前金币数left_idx, left_num = 0, 1  # 左边界right_idx, right_num = 0, 1  # 右边界# 一、 扩大窗口到 xwindow = 0while window < x and right_idx < n:if right_num == 1 and window + d[right_idx] <= x:coin_sum += (1 + d[right_idx]) * d[right_idx] / 2window += d[right_idx]right_idx += 1else:   # 按天进行右移右指针if right_num <= d[right_idx]:coin_sum += right_numwindow += 1right_num += 1if right_num > d[right_idx]:  # 当前月已过，跳到下个月right_idx += 1right_num = 1# 二、保持窗口(同时左右指针右移动)，尝试将最大金币数记录下来# 数据量较大，因此不能一步一步的移动max_coin = coin_sum  # 最大金币数while right_idx < n:left_step = d[left_idx] - left_num + 1     # 左指针可以移动的步数right_step = d[right_idx] - right_num + 1  # 右指针可以移动的步数step = min(left_step, right_step)  # 取最小步数# 总金币变化 = 右侧增加的金币 - 左侧减少的金币# coin_change = (right_num + right_num + step) * step / 2 - (left_num + left_num + step) * step / 2# = (right_num - left_num) * stepcoin_sum += (right_num - left_num) * stepmax_coin = max(max_coin, coin_sum)# 窗口向右移动 stepleft_num += stepright_num += stepif left_num > d[left_idx]:  # 当前月已过，跳到下个月left_idx += 1left_num = 1if right_num > d[right_idx]:  # 当前月已过，跳到下个月right_idx += 1right_num = 1return int(max_coin)if __name__ == "__main__":# 一年中的月数和连续登陆的天数n, x = map(int, input().split())# 每月份的天数d = list(map(int, input().split()))# 因为从年底再往后走又走到年初， 相当于一个环# 为了能遍历到所有的情况，将月份 * 2 进行处理print(solve(2 * n, x, d + d))