最大子矩阵和

Blah数集

大数学家高斯小时候偶然间发现一种有趣的自然数集合Blah，对于以a为基的集合Ba定义如下：
(1)a是集合Ba的基，且a是Ba的第一个元素；
(2)如果x在集合Ba中，则2x+1和3x+1也都在集合Ba中；
(3)没有其他元素在集合Ba中了。
现在小高斯想知道如果将集合Ba中元素按照升序排列，第N个元素会是多少？

暴力思路

i=1
q.push(a)
while(!q.empty() && i < N){
   x=q.pop() // 出队
   q.push(2x+1)
   q.push(3x+1)
   sort(q) // 入队的2x+1可能小于上次入队的3x+1（当N较大时可能会超时）
}
cout<<q.pop()

改进思路

1. 数组ba存放集合
2. 两个队列q1、q2，分别放2x+1、3x+1——保证2个队列各自严格升序
3. q1.push(a)、q2.push(a)
4. 每次分别取队头x1、x2，二者最小值x放入ba
5. 从q1或q2删除x（若x1==x2，则都删）
6. q1.push(2x+1)、q2.push(3x+1)
7. 最后输出ba[N]

while (cin >> a >> n) {
    queue<int> q1;
    queue<int> q2;
    q1.push(a);
    q2.push(a);
    for (int i = 1; i <= n; i++) {
        int e1 = q1.front();
        int e2 = q2.front();
        int min = e1 > e2 ? e2 : e1;
        if (e1 > e2) {
            q2.pop();
        } else if (e1 < e2) {
            q1.pop();
        } else {
            q1.pop();
            q2.pop();
        }
        arr[i] = min;
        q1.push(2 * min + 1);
        q2.push(3 * min + 1);
    }
    cout << arr[n] << endl;
}