中国银联-软件开发-笔试

发表于 更新于 分类于 ， 阅读次数： 本文字数： 863 阅读时长 ≈ 3 分钟

买古董

小明在古董市场上用手中的m元买东西，古董编号从0-10^9，编号=价格，小明手里已经有n件，小明不会重复购买，每件物品最多持有一个。帮小明计算手里的m元还能购买多少件？

输入 ：

第一行：小明已经拥有的股东数目n和手上的金额m

第二行：小明已经拥有的古董编号，每个编号以空格隔开，总共n个编号。

输出：小明以手里的m元还能买多少件古董。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def calculate_purchasable_antiques(n, m, owned_ids):
    owned_set = set(owned_ids)  # 将已拥有的古董编号放入集合
    purchasable_count = 0       # 可购买古董数量初始化为0
    current_price = 0           # 起始编号为0的古董

    # 依次尝试购买古董，直到金额不够或达到编号范围为止
    while m >= current_price and current_price <= 10**9:
        if current_price not in owned_set:  # 该编号的古董小明未拥有
            if m >= current_price:  # 检查金额是否足够
                m -= current_price  # 扣除金额
                purchasable_count += 1  # 增加可购买数量
            else:
                break  # 金额不足，退出循环
        current_price += 1  # 尝试购买下一个编号的古董

    return purchasable_count


# 获取输入
n, m = map(int, input().split())  # 第一行：小明已拥有的古董数量和手上的金额
owned_ids = list(map(int, input().split()))  # 第二行：小明已拥有的古董编号列表

# 计算小明可以购买的古董数量
result = calculate_purchasable_antiques(n, m, owned_ids)
print(result)

吃桃子的最小重量

这个题意不是非常明确。我没看明白题目意思。

小明在桌子上放了一排桃子，吃掉其中一个时，会同时吃掉相邻两个，否则宁可不吃。桃子重量不相同。怎么样才能使吃到的桃子总重量最少。

输入：

第一行，一个整数n，表示桃子总数

第二行，一个整数数组，表示桃子的不同重量

输出：一个整数，表示所吃桃子的最小总重量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def minWeight(n, weights):
    if n == 0:
        return 0
    if n == 1:
        return weights[0]
    
    # 初始化动态规划数组
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    
    # 状态转移
    for length in range(3, n + 1):  # 长度从3开始，因为至少需要3个桃子才能吃一个
        for i in range(1, n - length + 2):  # 从第1个桃子开始，确保有长度的空间
            j = i + length - 1  # 计算结束位置
            dp[i][j] = float('inf')
            for k in range(i, j - 1):  # 选择一个位置k来吃桃子
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 2][j] + weights[i - 1] + weights[k] + weights[j])
    
    return dp[1][n]

# 输入
n = int(input().strip())  # 桃子总数
weights = list(map(int, input().strip().split()))  # 桃子的重量

# 输出
print(minWeight(n, weights))

或者 GPT 的答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def min_weight_to_eat(n, weights):
    if n < 3:
        return 0  # 如果桃子少于3个，无法满足“吃掉相邻两个”的条件

    total_weight = 0  # 用于累加最小吃掉的桃子总重量
    eaten = [False] * n  # 记录每个桃子是否已被吃掉

    for i in range(1, n - 1):
        # 仅考虑还未吃掉的桃子及其相邻桃子
        if not eaten[i - 1] and not eaten[i] and not eaten[i + 1]:
            # 吃掉中间桃子，同时标记相邻桃子已被吃掉
            total_weight += weights[i]
            eaten[i - 1] = eaten[i] = eaten[i + 1] = True

    return total_weight


# 获取输入
n = int(input())  # 第一行：桃子总数
weights = list(map(int, input().split()))  # 第二行：桃子不同重量数组

# 计算并输出最小吃掉的桃子总重量
result = min_weight_to_eat(n, weights)
print(result)