题目链接

神奇苹果桶

题目描述

小希记录了一个神奇木桶中苹果数量的 次变化。初始时木桶为空（0个苹果）。共有三种操作类型：

  1. 类型1：木桶里增加了 个苹果。

  2. 类型2：有人想取走 个苹果，但只有当木桶中的苹果数不少于 时，该操作才会成功。若不成功，则一个苹果也不取。

  3. 类型3：小希取走木桶中 的苹果，如果数量不能整除，则向上取整。

需要计算出 次操作后，木桶中最终剩余的苹果数量。

思路分析

本题是一个直接的模拟题。我们需要做的就是维护一个变量来记录当前木桶中的苹果数量，然后根据输入的 次操作，逐一更新这个变量的值。

核心在于正确地实现三种操作的逻辑，并注意数据范围可能导致的问题。

  1. 变量定义：我们定义一个变量，例如 ，来存储苹果的数量，并将其初始值设为 。

  2. 数据类型选择：注意到题目中的 和 最大可达 。在最坏的情况下，可能会有 次增加苹果的操作，每次增加 个。这会导致苹果总数达到 ，这个值超过了标准32位整型（int）的存储范围。因此，我们必须使用64位整型（如C++中的 long long 或Java中的 long）来存储 ，以防止数据溢出。

  3. 操作逻辑实现：

    • 对于类型1的操作，直接执行加法：。

    • 对于类型2的操作，需要一个条件判断：if () { ; }。

    • 对于类型3的操作，关键是处理“向上取整”的除法。对于两个正整数 和 ， 可以用整型运算 (a + b - 1) / b 来实现。因此，需要取走的苹果数是 ( + - 1) / 。更新操作为 。

通过循环 次，依次执行上述逻辑，即可得到最终答案。

代码

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    long long apples = 0;
    for (int i = 0; i < n; ++i) {
        int type;
        long long x;
        cin >> type >> x;
        if (type == 1) {
            apples += x;
        } else if (type == 2) {
            if (apples >= x) {
                apples -= x;
            }
        } else { // type == 3
            if (x > 0) { // 防止除以0
                apples -= (apples + x - 1) / x;
            }
        }
    }
    cout << apples << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long apples = 0;
        for (int i = 0; i < n; i++) {
            int type = sc.nextInt();
            long x = sc.nextLong();
            if (type == 1) {
                apples += x;
            } else if (type == 2) {
                if (apples >= x) {
                    apples -= x;
                }
            } else { // type == 3
                if (x > 0) { // 防止除以0
                    apples -= (apples + x - 1) / x;
                }
            }
        }
        System.out.println(apples);
    }
}

n = int(input())
ops = list(map(int, input().split()))

apples = 0
for i in range(n):
    op_type = ops[2 * i]
    x = ops[2 * i + 1]

    if op_type == 1:
        apples += x
    elif op_type == 2:
        if apples >= x:
            apples -= x
    else: # op_type == 3
        if x > 0: # 防止除以0
            # // 是向下取整除法
            apples -= (apples + x - 1) // x

print(apples)

算法及复杂度

  • 算法：模拟

  • 时间复杂度：，其中 是操作的总次数。我们对每次操作进行一次常数时间的计算。

  • 空间复杂度：。除了输入数据外，我们只需要常数个变量来存储状态。如果将所有输入预先读入，则空间复杂度为 ，但这并非必要。