求助两道C++算法题

fiveeeee

题目描述
你有一个基于动态分配数组的顺序表。表中的元素均为非负整数，且按照非递减的顺序排列，即对于任何相邻的前后两个元素，靠前的元素都小于等于靠后的元素。

动态分配数组的规则如下：

初始时，表中元素个数为 0，数组的容量为 2。
每当在表已满（元素个数等于数组容量）的情况下尝试插入新的元素，则将动态分配的数组容量扩容为原来的 2 倍。此次插入操作造成的表中已有元素移动的次数等于此操作发生之前表中元素的个数（也即扩容前的数组的容量）。
每当在删除元素的操作之前，如果表中的元素个数小于等于数组容量的四分之一，则将动态分配的数组容量缩减为原来的一半。此次删除操作造成的表中已有元素移动的次数等于此操作发生之前表中元素的个数减 1（因为要删除的元素不需要被移动）。
如果某次插入或删除操作没有引起数组容量的变化，则：

对于插入元素的操作，此次操作造成的表中已有元素移动的次数等于插入的位置之后原有元素的个数。如果表中有相同元素导致可插入的位置不唯一，则选择最靠后的位置插入，以便减小表中已有元素移动的次数。
对于删除元素的操作，此次操作造成的表中已有元素移动的次数等于被删除的元素之后原有元素的个数。同样地，如果表中有多个相同的元素，则选择最靠后的元素删除，以便减小表中已有元素移动的次数。
现在，给出一系列的操作，每个操作可以是插入一个元素或删除一个元素（保证要删除的元素一定存在），请你输出每次操作造成的表中已有元素移动的次数。

输入格式
从标准输入读入数据。

第一行输入操作的总次数 n。

接下来 n 行，每行输入一个操作。操作的格式可能是：

A x 表示，在表中插入了一个值为 x 的元素；
D x 表示，在表中删除了一个值为 x 的元素。
输入的所有元素都在 unsigned int 范围内，即 0≤x<232。

输出格式
输出到标准输出。

对于每次操作，输出一行。每行仅包含一个整数，表示此次操作造成的表中已有元素移动的次数。

样例1输入
9
A 10
A 20
A 10
A 10
D 10
D 20
D 10
D 10
A 0
样例1输出
0
0
2
1
1
0
0
0
0
样例1解释
第 3 次操作导致数组容量从 2 变为 4，造成了 2 次表中已有元素移动；
第 4 次操作造成了元素 20 的 1 次表中已有元素移动；
第 5 次操作造成了元素 20 的 1 次表中已有元素移动；
第 8 次操作导致数组容量从 4 变为 2，但是没有发生表中已有元素移动。
样例2输入
17
A 1
A 2
A 3
A 4
A 5
A 6
A 7
A 8
A 9
D 9
D 8
D 7
D 6
D 5
D 4
D 3
D 2
样例2输出
0
0
2
0
4
0
0
0
8
0
0
0
0
0
3
0
1
子任务
在所有的数据中，操作次数 n≤10000。

对于前 20% 的数据，输入中仅包含插入操作，且每次插入的元素是递增的。

对于前 60% 的数据，输入中仅包含插入操作。

（有兴趣的同学，可以思考 n 如果在 106 左右的规模，此题该怎么做？）

提示
你可以按照题意实现一个符合要求的顺序表，也可以采用其他方式，只要能够正确输出答案即可。




篇幅太长，上传文件。

侃遍天下无二人

头一次见到求助还收费的

QingYi.

适合发悬赏

码上

侃遍天下无二人 发表于 2020-11-24 19:15
头一次见到求助还收费的

哈哈哈哈哈哈，应该新手我第一次也是

d0cklng

感觉题目比答案复杂， 我阅读了32.6%的题目后放弃了……