easy 与 hard 的唯一区别是 col[i] 的范围。

Tokitsukaze 正在玩一个消除游戏。

初始有 n 个宝石从左到右排成一排,第 i 个宝石的颜色为 col[i]。Tokitsukaze 可以进行若干次以下操作: 任选一种颜色 x,将颜色为 x 的最右边那颗宝石、以及该宝石右边的所有宝石全部消除。

Tokitsukaze 想知道至少需要几次操作才能把 n 个宝石全部消除。

输入格式

第一行包含一个整数 T (1 ≤ T ≤ 2⋅10^5),表示 T 组测试数据。

对于每组测试数据:

第一行包含一个整数 n (1 ≤ n ≤ 2⋅10^5),表示初始宝石的数量。

第二行包含 n 个整数 col_1, col_2, …, col_n (1 ≤ col_i ≤ min(n,2)),表示每个宝石的颜色。

保证 ∑n 不超过 2⋅10^5 。

输出格式

对于每组测试数据,输出一个整数,表示把 n 个宝石全部消除所需要的最少操作次数。

输入样例:

4
3
1 2 1
5
1 2 2 1 2
11
2 2 1 2 2 1 1 2 2 1 2
1
1

输出样例:

2
2
6
1

题目分析

分析题目我们可以知道,每次最优的选择是: 选择从右往左看最左边的第一次出现的宝石。

那么我们可以设法维护一个 从右往左看第一次出现的宝石 的集合。(从右往左遍历, 将第一次出现的宝石的坐标存到小根堆里,那么树根就是我们的最优选择)

那么怎么更新我们的这个小根堆呢?(选取树根进行消除操作后,小根堆的内容全部失效)

我们可以预先构造一个 ne 数组, 将每个位置的宝石的 ne 指向它的左边的第一个相同的宝石的位置。 那么在我们的消除操作后,我们只需要将小根堆全部倒出, 并按照 ne 构成下一个局面的从右往左看的第一次出现的宝石的小根堆集合。

接下来就是相同的迭代过程。

代码实现

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#define x first 
#define y second 
using namespace std;
using PII = pair <int,int>;
using LL = long long;
const int N = 2e5 + 10;

int t;
int solve() {
    int n, arr[N];
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> arr[i];
    priority_queue <PII, vector <PII>, greater <PII>> heap;
    unordered_map <int, int> fs, ne, ls;
    for (int i = n; i >= 1; --i) {
        if(fs.find(arr[i]) == fs.end()) {
            heap.push({i, arr[i]});
            fs[arr[i]] = i;
        }
    }
    for(int i = 1; i <= n; ++i) {
        if(ls.find(arr[i]) == ls.end()) {
            ls[arr[i]] = i;
            ne[i] = -1;
        }
        else {
            ne[i] = ls[arr[i]];
            ls[arr[i]] = i;
        }

    }
    int cnt = 0;
    int pos = n;
    while (pos >= 1) {
        ++cnt;
        priority_queue <PII, vector <PII>, greater <PII>> h;
        auto tt = heap.top();
        if(tt.x <= pos) pos = tt.x - 1;
        else break;
        while(!heap.empty()) {
            tt = heap.top(); heap.pop();
            int ps = tt.x, val = tt.y;
            while(tt.x > pos) tt.x = ne[tt.x];
            if(tt.x != -1) {
                h.push({tt.x, arr[tt.x]});
            }
        }
        heap = h;
    }
    return cnt;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while(t--) cout << solve() << '\n';
    return 0;
}

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status