题目链接

奶茶店特调

题目描述

在一家创意奶茶店，顾客可以定制由多种配料堆叠而成的“千层特调”。每种配料都有一个风味编号。

给定一个初始配方单，它包含了 层配料的风味编号和它们的添加顺序（从 到 ）。这个初始顺序号就是每层配料的“身份标识”。

制作过程中，顾客会提出 个“升级”请求，每个请求指定一个配料的身份标识。收到请求后，如果该配料还存在，它就会进入“待升级”状态，并可能与下方的配料层发生融合。

融合规则：

  1. 触发条件：一个“待升级”的配料层，如果其下方紧邻的配料层风味编号与它完全相同，两者将融合成一层。
  2. 融合效果：新配料的风味编号等于原风味编号加 1。
  3. 连锁反应：新融合的配料层将继承“待升级”状态，并立即尝试与它下方新的相邻层继续融合。这个过程会不断重复，直到它下方没有相同风味的配料，或者它已成为最底层。
  4. 隐藏款：通过融合产生的新配料层没有身份标识，因此不能被顾客的请求直接激活，但可以作为被动方参与由上层配料引发的融合。

任务： 完成所有顾客的“升级”请求后，计算奶茶最终还剩下多少层。

输入描述：

  • 第一行：整数 ，初始配料层数。
  • 第二行： 个整数，从下到上（索引 到 ）每一层配料的风味编号。
  • 第三行：整数 ，升级请求数量。
  • 第四行： 个整数，每个整数代表一个配料的身份标识。

输出描述：

  • 一个整数，代表最终剩余的配料层数。

解题思路

本题是一个精巧的模拟题，核心在于处理连锁的“融合”操作。我们需要一个动态的数据结构来表示奶茶的层次，并且需要区分每层配料的“风味”和它不变的“身份标识”。

  1. 数据结构选择：

    • 奶茶的层次是动态变化的，配料层会被移除，因此使用支持高效删除操作的数据结构比较理想，如 std::vector (C++), ArrayList (Java), 或 list (Python)。
    • 为了区分风味和身份，我们可以让列表中的每个元素都是一个复合结构，例如一个 pair 或一个简单的自定义对象，存储 {flavor, id}。
    • 对于融合后产生的新配料（隐藏款），我们可以为其分配一个特殊的 id，例如 -1，以表示它没有身份标识。

  2. 初始化：

    • 读取 和初始风味列表。
    • 构建我们的奶茶层级列表，其中第 i 个元素是 {flavor[i], i}，代表风味为 flavor[i]，身份标识为 i。

  3. 处理升级请求：

    • 遍历所有 个升级请求。对于每个请求 req_id：
    • 查找：首先，需要在当前的奶茶层级列表中找到身份标识为 req_id 的配料。这需要一次线性扫描，找到其在列表中的当前索引 idx。
    • 检查：如果找不到（说明该配料已被之前的融合操作移除了），则忽略此请求。
    • 触发融合：如果找到了，就从这个 idx 位置开始，启动一个连锁融合的循环。

  4. 连锁融合逻辑 (核心)：

    • 这是一个 while 循环，只要当前“待升级”层（索引为 idx）满足融合条件，循环就继续。
    • 融合条件：idx > 0 (不是最底层) 并且 layers[idx].flavor == layers[idx - 1].flavor。
    • 融合操作：
      • 更新下方配料层：layers[idx - 1].flavor++ 并且 layers[idx - 1].id = -1 (变为隐藏款)。
      • 移除当前配料层：从列表中删除 layers[idx]。
      • 状态继承：融合后的新层（现在位于 idx - 1）成为新的“待升级”层。因此，在下一次循环检查之前，我们将 idx 更新为 idx - 1。
    • 当 while 循环的条件不再满足时，连锁反应结束，处理下一个升级请求。

  5. 最终结果：

    • 处理完所有 个请求后，奶茶层级列表的最终大小 layers.size() 就是答案。

复杂度分析：

  • 设 为初始层数， 为请求数。
  • 对于每个请求，查找目标 id 的时间是 。
  • 关键在于融合操作的总次数。每一次融合都会使总层数减 1。因此，在所有 次请求中，融合操作总共最多发生 次。
  • 如果使用 vector 或 ArrayList，单次删除操作是 。因此，所有融合操作的总成本是 。
  • 总时间复杂度 = 查找成本 + 总融合成本 = 。
  • 给定 ，这个复杂度是完全可以接受的。

代码

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

struct Layer {
    int flavor;
    int id;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<Layer> layers(n);
    for (int i = 0; i < n; ++i) {
        cin >> layers[i].flavor;
        layers[i].id = i;
    }

    int m;
    cin >> m;

    for (int k = 0; k < m; ++k) {
        int req_id;
        cin >> req_id;

        int current_idx = -1;
        // 查找具有请求ID的层的当前索引
        for (int i = 0; i < layers.size(); ++i) {
            if (layers[i].id == req_id) {
                current_idx = i;
                break;
            }
        }

        if (current_idx != -1) {
            // 开始连锁融合
            while (current_idx > 0 && layers[current_idx].flavor == layers[current_idx - 1].flavor) {
                // 更新下方层
                layers[current_idx - 1].flavor++;
                layers[current_idx - 1].id = -1; // 变为隐藏款
                
                // 移除当前层
                layers.erase(layers.begin() + current_idx);
                
                // 新的待升级层是融合后的下方层
                current_idx--;
            }
        }
    }

    cout << layers.size() << endl;

    return 0;
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Layer {
    int flavor;
    int id;

    Layer(int flavor, int id) {
        this.flavor = flavor;
        this.id = id;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        List<Layer> layers = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            layers.add(new Layer(sc.nextInt(), i));
        }

        int m = sc.nextInt();
        for (int k = 0; k < m; k++) {
            int reqId = sc.nextInt();

            int currentIdx = -1;
            // 查找具有请求ID的层的当前索引
            for (int i = 0; i < layers.size(); i++) {
                if (layers.get(i).id == reqId) {
                    currentIdx = i;
                    break;
                }
            }
            
            if (currentIdx != -1) {
                // 开始连锁融合
                while (currentIdx > 0 && layers.get(currentIdx).flavor == layers.get(currentIdx - 1).flavor) {
                    // 获取下方层
                    Layer bottomLayer = layers.get(currentIdx - 1);
                    
                    // 更新下方层
                    bottomLayer.flavor++;
                    bottomLayer.id = -1; // 变为隐藏款
                    
                    // 移除当前层
                    layers.remove(currentIdx);
                    
                    // 新的待升级层是融合后的下方层
                    currentIdx--;
                }
            }
        }

        System.out.println(layers.size());
    }
}

def solve():
    # 读取初始配方
    n = int(input())
    flavors = list(map(int, input().split()))
    
    # 构建层级列表，每个元素为 [flavor, id]
    layers = [[flavors[i], i] for i in range(n)]
    
    # 读取请求
    m = int(input())
    requests = list(map(int, input().split()))
    
    for req_id in requests:
        current_idx = -1
        # 查找具有请求ID的层的当前索引
        for i in range(len(layers)):
            if layers[i][1] == req_id:
                current_idx = i
                break
        
        if current_idx != -1:
            # 开始连锁融合
            while current_idx > 0 and layers[current_idx][0] == layers[current_idx - 1][0]:
                # 更新下方层
                layers[current_idx - 1][0] += 1
                layers[current_idx - 1][1] = -1 # 变为隐藏款
                
                # 移除当前层
                layers.pop(current_idx)
                
                # 新的待升级层是融合后的下方层
                current_idx -= 1
    
    print(len(layers))

solve()

算法及复杂度

  • 算法：本题是一个模拟题，核心是处理连锁的“融合”操作。我们使用一个列表来动态维护奶茶的层次结构，列表中的每个元素同时记录其“风味”和“原始身份标识”。对于每个升级请求，我们先找到对应身份的配料层，然后在一个循环中模拟其与下层配料的连锁融合反应，直到不满足融合条件为止。

  • 时间复杂度：。其中 是初始配料层数， 是请求数量。

    • 对于 个请求中的每一个，都需要 的时间来查找目标配料的当前位置。这部分总时间是 。
    • 融合操作会导致列表元素减少。每一次融合操作，如果使用 vector 或 ArrayList，删除元素的时间复杂度是 。由于最多只能发生 次融合（每次融合消耗一层），所有融合操作的总时间成本上限为 。
    • 因此，总时间复杂度为这两部分之和。

  • 空间复杂度：。主要空间开销用于存储奶茶的层级列表，其中最多包含 个元素。