一本通-1333：【例2-2】Blah数集（优先级队列模拟）

【题目描述】 大数学家高斯小时候偶然间发现一种有趣的自然数集合Blah，对于以a为基的集合Ba定义如下：

(1)a是集合Ba的基，且a是Ba的第一个元素；

(2)如果x在集合Ba中，则2x+1和3x+1也都在集合Ba中；

(3)没有其他元素在集合Ba中了。

现在小高斯想知道如果将集合Ba中元素按照升序排列，第N个元素会是多少？

【输入】 输入包括很多行，每行输入包括两个数字，集合的基a(1≤a≤50))以及所求元素序号n(1≤n≤1000000)。

【输出】 对于每个输入，输出集合Ba的第n个元素值。

【输入样例】 1 100 28 5437

【输出样例】 418 900585

---

#include <bits/stdc++.h>

using namespace std;

long long a, k;
vector<long long> seq(1000005);

long long solve()
{
    int rear = 2;
    seq[1] = a;
    int two = 1, three = 1;
    while (rear <= k) {
        long long tmp1 = seq[two] * 2 + 1;
        long long tmp2 = seq[three] * 3 + 1;
        long long res = min(tmp1, tmp2);
        if (tmp1 < tmp2) ++two;
        else ++three;

        if (res == seq[rear - 1]) continue;
        else seq[rear++] = res;
    }

    return seq[k];
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    while (cin >> a >> k) {
        cout << solve() << endl;
    }

    return 0;
}

这道题和洛谷-P1323 删数有一些类似，在洛谷的题目里我们使用优先级队列来生成数据，这里如果也使用优先级队列，会发现结果不一致。在洛谷里面，我们没有去考虑会不会产生重复数字的情况，而本题的集合里面是不能包含重复数字的。不能包含重复数字，且描述的是有序集合，第一个想到的是使用set，每次用迭代器取出首元素，然后再插入两个新元素。但是在本题使用set会超时。

除了第一个元素外，集合的一部分数字可以表示成2 * x + 1，一部分可以表示成 3 * x + 1，就有些类似队列的味道。每次取出两个集合最小的两个数字比较，取出最小的，但是注意要和队列的尾端去比较看是否重复。