小米笔试

第一题 爬山

首先俺们的Bob在一个风和日丽的日子选择去登珠峰，我们需要在n个特殊的日子（人话就是n天时间内）在大本营找到合适的时间去登山。但是需要知道补给只能维持k天，所以Bob最多只能待k天时间，所以他可能会在不适合爬山的日子撤回到低海拔地区。下撤是需要考虑移动次数的。

所以我们需要算的就是他在低海拔出发低海拔结束，在不错过n个日子且在大本营生活天数不超过k天的前提下最少的移动次数是多少。

思路

首先我们将输入进行拆分，举个例子，[2,3,4,7,8]五天时间，我们拆分为[2,3,4]和[7.8]两个区间，每个连续区间内他都只需要进入一次大本营，离开一次，所以我们区间数（最开始统计到的连续区间）p就是至少需要移动的一半。

接下来我们来优化移动次数

设p为最开始的连续区间数，假设我们停留k天，有n天时间登山，实际上额外停留时间为k - n。所以现在计算非登山日的间隔天数，我们将间隔从小到大排序，尽可能多利用可用额外的停留天数来减少p。具体操作为：

从最小的间隔开始，如果还能住，就可以减少一次移动机会（即合并两个区间），直到不能合并就可以得到p的最后结果即移动次数。

代码逻辑

1.统计区间数p：遍历数组，找到项链的两个登山日间隔如果不连续就增加数量。

2.计算可优化的间隔天数：统计所有间隔的长度并排序，计算能合并的区间，减少区间数p

3.计算最终移动次数：最少移动次数 = 2 * p（这里千万别忘了！）

代码

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    p = 1
    gaps = []
    for i in range(n - 1):
        if a[i + 1] > a[i] + 1:
            p += 1
            gaps.append(a[i + 1] - a[i] - 1)
    if p == 1:
        m = 1
    else:
        gaps.sort()
        allowed = k - n

        q = 0
        total_gap = 0
        for gap in gaps:
            if total_gap + gap <= allowed:
                total_gap += gap
                q += 1
            else:
                break
        m = p - q
    moves = 2 * m
    print(moves)
if __name__ == '__main__':
    main()

第二题 买车

某人要去买车，需要保证载X人，拉货Y吨，有n种车。

对第i种车价值mi元，有ki种方案，默认拉人xi，拉货yi。第i种方案需要mij元，可以选配件让拉人为xij拉货为yij。但是只能选一种。然后要买多种车需要最少的钱。

思路

相信所有人百分百第一眼看到这题第一反应是，这人有毛病吧！

好我们梳理一下

首先，问题就是至少载X人，至少载Y吨货，然后花费最少。

可以选择的方案有多种，最基本的为mi元，xi人，yi吨。或者别的。

解决方案：

我们把每种汽车和方案都看成一个“物品”，费用就是汽车的价格，收益就是购买某个汽车后它有一定的承载能力。也就是说我们可以直接转化为一个二维费用的完全背包问题。

对于该问题直接采用动态规划。

假设$dp[x][y]$满足至少x人y吨且花费最小

接下来定义方程

最开始$dp[0][0]=0$即初始状态。

依次遍历所有的方案（cost, cap_x, cap_y）：

​ 完全背包的思想：同一种车买多次，每次购买都会增加承载能力

​ 朴素的完全背包思想：从小到大遍历x, y：$dp[min(X, x + cap_x)][min(Y, y + cap_y)] = min(dp[min(X,x+cap_x)][min(Y,y+cap_y)],dp[x][y]+cost)$

计算过程就是累计遍历所有的方案逐步更新dp，最后得到的就是最小花费。

这里需要注意我们最后如果值依旧是无穷大则说明无法满足直接返回 -1。

代码解析

1.读取输入并初始化DP：初始化$dp[x][y]$为 inf，表示当前需求未被满足。dp[0][0]表示初始化无需花费。

2.处理所有的基础配置和方案：将默认的方案加入all_configs 。读取其他方案并在计算后加入all_configs。

3.使用动态规划来计算最小花费：遍历数组，用所有配置来更新 dp[x][y]。用完全背包方法，即允许重复购买同一车辆（从(x,y)开始尝试购买更多同一车辆方案并不断更新。

4.如果最后得到的依旧是 inf则输出-1否则输出正确结果。

注意

这里我最后没有完全做对，但思路是这个，最后我是超时了只有70%。如果有直接做对的可以评论下。

代码

def main():
    X, Y, n = map(int, input().split())
    inf = float('inf')
    dp = [[inf for _ in range(Y + 1)] for _ in range(X + 1)]
    dp[0][0] = 0
    all_configs = []
    for _ in range(n):
        line = list(map(int, input().split()))
        base_cost, base_x, base_y, k = line
        if base_x > 0 and base_y > 0:
            all_configs.append((base_cost, base_x, base_y))

        for _ in range(k):
            m_opt, x_opt, y_opt = map(int, input().split())
            total_cost = base_cost + m_opt
            total_x = base_x + x_opt
            total_y = base_y + y_opt

            if total_x > 0 and total_y > 0:
                all_configs.append((total_cost, total_x, total_y))
    for x in range(X + 1):
        for y in range(Y + 1):
            if dp[x][y] == inf:
                continue
            for cost, cap_x, cap_y in all_configs:
                curr_x = x
                curr_y = y
                curr_cost = dp[x][y]
                while True:
                    next_x = min(X, curr_x + cap_x)
                    next_y = min(Y, curr_y + cap_y)
                    if next_x == curr_x and next_y == curr_y:
                        break
                    curr_cost += cost
                    dp[next_x][next_y] = min(dp[next_x][next_y], curr_cost)
                    curr_x = next_x
                    curr_y = next_y
                    if curr_x == X and curr_y == Y:
                        break
    result = dp[X][Y]
    print(result if result!= inf else -1)
if __name__ == '__main__':
    main()