2023.09.23-秋招-第二题-塔子哥的迷宫

2

wangxuehui LV 9 @ 8 months ago

#include <algorithm>
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main(){
    int m;
    cin>>m;
    vector<vector<int>> g(2,vector<int>(m));
    vector<vector<int>> pre_sum(2,vector<int>(m,0));//每一行的前缀和
    for (int i=0; i<2; i++) {
        for (int j=0; j<m; j++) {
            cin>>g[i][j];
            if (j>0) {
                pre_sum[i][j]=pre_sum[i][j-1]+g[i][j];
            }else {
                pre_sum[i][j]=g[i][j];
            }
        }
    }
    //判断小A在哪一列转弯，并且让b最小，最好的办法记录每次小A转弯，小b能够走的路的最大的值集合，
    //但是取最大值中最小的，因为小A 要尽量减少小B吃掉的糖果总数
    int res=INT_MAX;
    for (int j=0; j<m; j++) {
        int a0=pre_sum[0][m-1]-pre_sum[0][j];
        int a1=0;
        if (j>0) {
            a1=pre_sum[1][j-1];
        }
        int ben_max=max(a0,a1);
        res=min(res,ben_max);
    }
    cout<<res<<endl;
}

0

老友人来人往 LV 7 @ 6 months ago

m = int(input())
matrix = [list(map(int,input().split())) for _ in range(2)]
ljh = [[0]*(m+1) for _ in range(2)]
ans = float('inf')
for i in range(m):
    ljh[0][i+1] = ljh[0][i]+matrix[0][i]
    ljh[1][i+1] = ljh[1][i]+matrix[1][i]
for i in range(1,m+1):
    sorce = max(ljh[1][i-1],ljh[0][m]-ljh[0][i])
    ans = min(ans,sorce)
print(ans)

0

TaZi SU @ 9 months ago

题面描述

在一个包含两行和m列的糖果迷宫中，小A和小B从左上角出发，目标是到达右下角。小A在路径中尽量减少小B可以获得的糖果，而小B希望在小A走完后能尽可能多地吃到糖果。通过动态规划的方法，我们可以计算出小B最多能够吃掉的糖果数量。具体实现时，首先记录小A的路径及其获得的糖果，然后基于小A的路径计算小B的最大糖果数，最终得出小B可以获得的最大糖果总数。

题目分析

我们需要计算小A和小B分别在迷宫中移动时所能吃到的糖果数量。小A从左上角开始，向右或向下移动，直到到达终点。小B则从小A结束的地方开始，从终点位置返回到左上角，但不能吃小A吃过的糖果。小A的目标是尽量减少小B吃掉的糖果，而小B希望在小A走完后能吃到尽可能多的糖果。

思路

前缀和的计算：
- 我们需要计算小A和小B在每一列之前吃掉的糖果和。通过前缀和数组，我们能够快速获得任意区间内的糖果总数。
- 对于每一行，建立一个前缀和数组qzs，其中qzs[i][j]表示第i行前j列的糖果总和。这样可以方便地计算出小A和小B在任意分割点之前和之后的糖果数量。
分割点的选择：
- 小A从左上角出发到达某个分割点，然后停止，接着小B从该分割点开始向右走至终点。在这个过程中，我们需要考虑每一个可能的分割点。
- 对于每一个分割点i，小A在分割点之前的总糖果数为qzs[0][i + 1]（第一行的前缀和），而小B在该分割点之后的糖果数则为qzs[1][m] - qzs[1][i]（第二行的前缀和减去分割点的糖果）。
最小化最大值：
- 对于每个分割点，计算小A在分割点之前和小B在分割点之后所能吃到的糖果数量。我们需要找出小B可能吃到的最大糖果数，并对所有分割点的结果取最小值。这样可以确保小A所吃的糖果数量最小化时，小B所能获得的糖果数量最大。
代码实现：
- 代码中首先读取糖果迷宫的数据，计算前缀和，然后遍历每一个可能的分割点，计算相应的糖果数量，最后输出小B能够吃到的最大糖果数。

时间复杂度

整个算法的时间复杂度为 (O(m))，因为我们只需遍历一次二维数组来计算前缀和，另外一次遍历进行计算，整体为线性复杂度。

代码实现

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int m;
    cin >> m;
    
    // 初始化糖果迷宫和前缀和数组
    vector<vector<int>> grid(2, vector<int>(m));
    vector<vector<int>> qzs(2, vector<int>(m + 1));
    
    // 读取第一行糖果并计算前缀和
    for (int j = 0; j < m; j++) {
        cin >> grid[0][j];
        qzs[0][j + 1] = qzs[0][j] + grid[0][j];
    }
    
    // 读取第二行糖果并计算前缀和
    for (int j = 0; j < m; j++) {
        cin >> grid[1][j];
        qzs[1][j + 1] = qzs[1][j] + grid[1][j];
    }
    
    // 初始化最小糖果损失值为较大数
    long long ans = INT_MAX;
    
    // 遍历每个分割点，从0到m-1
    for (int i = 0; i < m; i++) {
        // 计算小B在该分割点的最大可能值
        int tmp = max(qzs[1][i], qzs[0][m] - qzs[0][i + 1]);
        // 更新答案，取最小值
        ans = min(ans, static_cast<long long>(tmp));
    }
    
    // 输出小B最多能吃到的糖果数量
    cout << ans << endl;
    
    return 0;
}

Python 代码

# 输入迷宫的列数
m = int(input())
# 读取糖果分布并初始化前缀和数组
grid = [list(map(int, input().split())) for _ in range(2)]

# 初始化前缀和数组
qzs = [[0] * (m + 1) for _ in range(2)]
for j in range(m):
    # 计算第一行前缀和
    qzs[0][j + 1] = qzs[0][j] + grid[0][j]
    # 计算第二行前缀和
    qzs[1][j + 1] = qzs[1][j] + grid[1][j]

# 设定答案为一个较大的值
ans = float('inf')
# 遍历所有分割点，找到最优分割
for i in range(1, m + 1):
    # 计算小B在当前分割点的最优结果
    tmp = max(qzs[1][i - 1], qzs[0][m] - qzs[0][i])
    # 更新最优解
    ans = min(ans, tmp)

# 输出小B最多可以吃到的糖果数
print(ans)

Java 代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        
        // 初始化糖果迷宫和前缀和数组
        int[][] grid = new int[2][m];
        int[][] qzs = new int[2][m + 1];
        
        // 读取第一行糖果并计算前缀和
        for (int j = 0; j < m; j++) {
            grid[0][j] = sc.nextInt();
            qzs[0][j + 1] = qzs[0][j] + grid[0][j];
        }
        
        // 读取第二行糖果并计算前缀和
        for (int j = 0; j < m; j++) {
            grid[1][j] = sc.nextInt();
            qzs[1][j + 1] = qzs[1][j] + grid[1][j];
        }

        // 初始化最小糖果损失值为较大数
        long ans = Integer.MAX_VALUE;
        
        // 遍历每个分割点，从0到m-1
        for (int i = 0; i < m; i++) {
            // 计算小B在该分割点的最大可能值
            int tmp = Math.max(qzs[1][i], qzs[0][m] - qzs[0][i + 1]);
            // 更新答案，取最小值
            ans = Math.min(ans, tmp);
        }

        // 输出小B最多能吃到的糖果数量
        System.out.println(ans);
    }
}

代码注释总结

前缀和数组：qzs[0][j+1] 记录小A在迷宫第0行的糖果和，qzs[1][j+1] 记录小B在迷宫第1行的糖果和。
分割点循环：遍历每一个可能的分割点，通过比较小B和小A的前缀和，计算当前点的最小损失值。
更新和输出：在遍历完所有列后，输出小B的最大糖果数量。

3 solutions

题面描述

题目分析

思路

时间复杂度

代码实现

C++ 代码

Python 代码

Java 代码

代码注释总结

Information

Status

Development

Support