AOJ 898.黑匣子|OhYee 博客

这是一篇最后编辑于 8 年前的文章，其内容可能与目前实际情况差异较大，请注意甄别

题目

{% fold 点击显/隐题目 %}

Description 我们使用黑匣子的一个简单模型。它能存放一个整数序列和一个特别的变量i。在初始时刻，黑匣子为空且i等于0。这个黑匣子能执行一系列的命令。有两类命令： ADD(x)：把元素x放入黑匣子；GET：把i加1的同时，输出黑匣子内所有整数中第i小的数。牢记第i小的数是当黑匣子中的元素已非降序排序后位于第i位的元素。下面的表是一个11个命令的例子：

现需要一个有效的算法处理给定的一系列命令。ADD和GET命令的总数至多个有30000个。定义ADD命令的个数为M个，GET命令的个数为N个。我们用下面得两个整数序列描述命令序列：
1．A(1),A(2),……,A(M)：加入黑匣子的元素序列。所有的数均为绝对值不超过2000000的整数。例如在上例中A=(3,1,-4,2,8,-1000,2)。
2．u(1),u(2),……,u(N)：u(i)表示第i个GET命令在第u(i)个ADD命令之后，例如在上例中，u=(1,2,6,6)。
你可以假定自然数序列u(1),u(2),……,u(N)以非降序排列，N≤M，且对于每一个p（1≤p≤N）有p≤u(p)≤M。

第一行存放M和N的值,第二行存放 A(1),A(2),……,A(M) ,第三行存放u(1),u(2),……,u(N)。

输出黑匣子的处理结果。

7 4 3 1 -4 2 8 -1000 2 1 2 6 6

3 3 1 2

{% endfold %}

题解

用vector模拟所有操作即可,复杂度有点高不过能过

代码

{% fold 点击显/隐代码 %}```cpp 黑匣子 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
//
#define debug
#include
///
#include
#include
#include
#include
#include
using namespace std;

const int maxn = 30005;
int A[maxn];
int U[maxn];

int main() {
#ifdef debug
freopen("in.txt", "r", stdin);
int START = clock();
#endif
cin.tie(0);
cin.sync_with_stdio(false);

int m, n;
while (cin >> m >> n) {
    for (int i = 0; i < m; i++)
        cin >> A[i];

    for (int i = 0; i < n; i++)
        cin >> U[i];

    sort(U, U + n);

    vector<int> v;
    int I = 0;
    int getNum = 0, addNum = 0;
    for (int i = 0; i < n + m; i++) {
        if (U[getNum] == addNum) {
            //cout << "Get(" << I << ")" << endl;
            cout << v[I++] << endl;
            getNum++;
            if (getNum >= n)
                break;
        } else {
            //cout << "Add(" << A[addNum] << ")  ";

            v.insert(lower_bound(v.begin(), v.end(), A[addNum]), A[addNum]);

            // for (size_t i = 0; i < v.size(); i++)
            //     cout << v[i] << " ";
            // cout << endl;

            addNum++;
        }
    }
}

#ifdef debug
printf("Time:%.3fs.\n", double(clock() - START) / CLOCKS_PER_SEC);
#endif
return 0;
}

{% endfold %}

推荐订阅源

OhYee 博客

题目

题解

代码