Bailian3728 Blah数集【数学+set】

3728:Blah数集
总时间限制: 3000ms 内存限制: 65536kB
描述
大数学家高斯小时候偶然间发现一种有趣的自然数集合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

问题链接：Bailian3728 Blah数集
问题简述：（略）
问题分析：求2个函数最小值问题，逐步生成元素即可。用STL的set来实现似乎会超时，贴出代码做个参考。
程序说明：（略）
参考链接：（略）
题记：（略）

AC的C++语言程序如下：

/* Bailian3728 Blah数集 */

#include <stdio.h>

#define N 1000000
int v[N + 1];

int main(void)
{
    int a, n, i, k2, k3, a2, a3;
    while(~scanf("%d%d", &a, &n)) {
        v[1] = a, i = 1, k2 = 1; k3 = 1, a2 = a * 2 + 1, a3 = a * 3 + 1;
        for(;;) {
            if(a2 < a3)
                v[++i] = a2, a2 = v[++k2] * 2 + 1;
            else if(a2 > a3)
                v[++i] = a3, a3 = v[++k3] * 3 + 1;
            else /* if(a2 == a3) */
                v[++i] = a2, a2 = v[++k2] * 2 + 1, a3 = v[++k3] * 3 + 1;

            if(i == n) {
                printf("%d\n", v[i]);
                break;
            }
        }
    }

    return 0;
}

TLE的C++语言程序如下：

/* Bailian3728 Blah数集 */

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int a, n;

    while(~scanf("%d%d", &a, &n)) {
        set<int> st;

        st.insert(a);
        set<int>::iterator iter = st.begin();

        int cnt = 0;
        while(++cnt < n) {
            st.insert(*iter * 2 + 1);
            st.insert(*iter * 3 + 1);
            iter++;
        }

        printf("%d\n", *iter);
    }

    return 0;
}