题目
{% fold 点击显/隐题目 %}
现需要一个有效的算法处理给定的一系列命令。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。
题解
用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 %}