奶茶店特调

题目分析

有 层奶茶原料从底到顶排列，每层有一个风味编号和一个身份编号（初始位置 到 ）。执行 次"升级"操作，每次指定某个身份编号的层进行升级：

  1. 若该层正下方有一层风味编号相同，则两层融合为一层，新层风味编号 。
  2. 新层继承升级状态，继续尝试与下方融合，直到下方不存在或风味不同。
  3. 融合产生的新层没有身份编号，不能被直接指定升级，但可以被动参与后续融合。

如果某个身份编号的层已经在之前的融合中被消耗，则跳过该次操作。求所有操作结束后剩余层数。

思路

链表模拟

核心观察：每次升级操作是一个向下的链式融合过程——找到目标层，不断检查正下方的层是否风味相同，相同则融合。这要求我们能高效地查找某层的上下邻居，以及在中间插入/删除节点。

使用双向链表维护所有存活的层：

  • 每个节点记录：风味编号、前驱（下方）、后继（上方）。
  • 用 id_to_node 数组记录每个身份编号对应的节点。
  • 融合时，将当前层和下方层都标记为死亡，创建一个新节点（风味 ），接入链表中替代被删除的两个节点的位置。
  • 新节点作为当前层继续向下检查。

每次融合减少一层（两层变一层），总融合次数不超过 ，因此总节点数不超过 。

代码

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

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

    int n;
    cin >> n;

    vector<int> flavor(n);
    vector<int> prv(n, -1), nxt(n, -1);
    vector<bool> alive(n, true);
    vector<int> id_to_node(n);

    for(int i = 0; i < n; i++){
        cin >> flavor[i];
        id_to_node[i] = i;
        if(i > 0){
            prv[i] = i - 1;
            nxt[i - 1] = i;
        }
    }

    int total = n;
    int node_cnt = n;

    flavor.reserve(2 * n);
    prv.reserve(2 * n);
    nxt.reserve(2 * n);
    alive.reserve(2 * n);

    int m;
    cin >> m;

    while(m--){
        int identity;
        cin >> identity;

        int cur = id_to_node[identity];
        if(!alive[cur]) continue;

        while(true){
            int below = prv[cur];
            if(below == -1) break;
            if(flavor[below] != flavor[cur]) break;

            int new_f = flavor[cur] + 1;
            int pp = prv[below];
            int nn = nxt[cur];

            alive[cur] = false;
            alive[below] = false;
            total -= 2;

            int nd = node_cnt++;
            flavor.push_back(new_f);
            prv.push_back(pp);
            nxt.push_back(nn);
            alive.push_back(true);
            if(pp != -1) nxt[pp] = nd;
            if(nn != -1) prv[nn] = nd;
            total++;

            cur = nd;
        }
    }

    cout << total << endl;
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer st = new StreamTokenizer(br);

        st.nextToken(); int n = (int) st.nval;

        int[] flavor = new int[2 * n];
        int[] prv = new int[2 * n];
        int[] nxt = new int[2 * n];
        boolean[] alive = new boolean[2 * n];
        int[] idToNode = new int[n];

        Arrays.fill(prv, -1);
        Arrays.fill(nxt, -1);

        for (int i = 0; i < n; i++) {
            st.nextToken();
            flavor[i] = (int) st.nval;
            alive[i] = true;
            idToNode[i] = i;
            if (i > 0) {
                prv[i] = i - 1;
                nxt[i - 1] = i;
            }
        }

        int total = n;
        int nodeCnt = n;

        st.nextToken(); int m = (int) st.nval;

        for (int q = 0; q < m; q++) {
            st.nextToken();
            int identity = (int) st.nval;

            int cur = idToNode[identity];
            if (!alive[cur]) continue;

            while (true) {
                int below = prv[cur];
                if (below == -1) break;
                if (flavor[below] != flavor[cur]) break;

                int newF = flavor[cur] + 1;
                int pp = prv[below];
                int nn = nxt[cur];

                alive[cur] = false;
                alive[below] = false;
                total -= 2;

                int nd = nodeCnt++;
                flavor[nd] = newF;
                prv[nd] = pp;
                nxt[nd] = nn;
                alive[nd] = true;
                if (pp != -1) nxt[pp] = nd;
                if (nn != -1) prv[nn] = nd;
                total++;

                cur = nd;
            }
        }

        System.out.println(total);
    }
}

import sys
input = sys.stdin.readline

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

    prv = [-1] * (2 * n)
    nxt = [-1] * (2 * n)
    flav = [0] * (2 * n)
    alive = [False] * (2 * n)
    id_to_node = [0] * n

    for i in range(n):
        flav[i] = flavors[i]
        alive[i] = True
        id_to_node[i] = i
        if i > 0:
            prv[i] = i - 1
            nxt[i - 1] = i

    total = n
    node_cnt = n

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

    for identity in ops:
        cur = id_to_node[identity]
        if not alive[cur]:
            continue

        while True:
            below = prv[cur]
            if below == -1:
                break
            if flav[below] != flav[cur]:
                break

            new_f = flav[cur] + 1
            pp = prv[below]
            nn = nxt[cur]

            alive[cur] = False
            alive[below] = False
            total -= 2

            nd = node_cnt
            node_cnt += 1
            flav[nd] = new_f
            prv[nd] = pp
            nxt[nd] = nn
            alive[nd] = True
            if pp != -1:
                nxt[pp] = nd
            if nn != -1:
                prv[nn] = nd
            total += 1

            cur = nd

    print(total)

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', l => lines.push(l.trim()));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const flavors = lines[1].split(' ').map(Number);
    const m = parseInt(lines[2]);
    const ops = lines[3].split(' ').map(Number);

    const maxNodes = 2 * n;
    const flav = new Int32Array(maxNodes);
    const prv = new Int32Array(maxNodes).fill(-1);
    const nxt = new Int32Array(maxNodes).fill(-1);
    const alive = new Uint8Array(maxNodes);
    const idToNode = new Int32Array(n);

    for (let i = 0; i < n; i++) {
        flav[i] = flavors[i];
        alive[i] = 1;
        idToNode[i] = i;
        if (i > 0) {
            prv[i] = i - 1;
            nxt[i - 1] = i;
        }
    }

    let total = n;
    let nodeCnt = n;

    for (const identity of ops) {
        let cur = idToNode[identity];
        if (!alive[cur]) continue;

        while (true) {
            const below = prv[cur];
            if (below === -1) break;
            if (flav[below] !== flav[cur]) break;

            const newF = flav[cur] + 1;
            const pp = prv[below];
            const nn = nxt[cur];

            alive[cur] = 0;
            alive[below] = 0;
            total -= 2;

            const nd = nodeCnt++;
            flav[nd] = newF;
            prv[nd] = pp;
            nxt[nd] = nn;
            alive[nd] = 1;
            if (pp !== -1) nxt[pp] = nd;
            if (nn !== -1) prv[nn] = nd;
            total++;

            cur = nd;
        }
    }

    console.log(total);
});

复杂度分析

  • 时间复杂度：。每次融合消耗两个节点产生一个新节点，总融合次数不超过 （因为层数单调减少），所以所有操作中 while 循环的总迭代次数为 。
  • 空间复杂度：。链表节点总数不超过 。