题解 | 奶茶店特调

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, m, a[N], pre[N];

int main() {
    ios :: sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for(int i=0; i<n; i++) cin >> a[i], pre[i] = i - 1;
    cin >> m;
    while( m -- ) {
        int u; cin >> u;
        int p = pre[u];
        while(p != -1 && a[p] == a[u]) {
            a[u] ++;
            pre[u] = pre[p];
            p = pre[p];
        }
    }
    int res = 0, p = n - 1;
    while(p != -1) {
        res ++;
        p = pre[p];
    }
    cout << res;
    return 0;
}

用类似链表的方式处理，感觉时间复杂度是O(N)