数据结构---set篇
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
第一次超时是因为用
m
e
m
s
e
t
memset
memset不得不超时第二次超时是我用
v
e
c
t
o
r
vector
vector数组的时候然后以
O
(
n
)
O(n)
O(n)复杂度查找元素之后使用
e
r
a
s
e
erase
erase方法进行删除第三次超时是我把查找元素改成了
O
(
l
o
g
n
)
O(logn)
O(logn)之后用
v
e
c
t
o
r
vector
vector的
e
r
a
s
e
erase
erase进行删除
A
C
AC
AC是我使用
s
e
t
set
set数据结构。
后来经过查阅资料
在
v
e
c
t
o
r
vector
vector当中删除元素需要经过内存的
O
(
n
)
O(n)
O(n)拷贝而
s
e
t
set
set远远不用利用红黑树维护的话最大也是
O
(
l
o
g
n
)
O(logn)
O(logn)找到位置再旋转
O
h
Oh
Oh我又想起那段实现红黑树可怕的日子。
关于这个题我一开始想从前向后贪心但是这会涉及到一个问题前面如果都放小的那么到最后把大的放后面可能无解。所以从后往前贪心呗。参考题解
代码
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
const int length = 2e5 + 5;
int num[length];
int main(void)
{
int t;
scanf_s("%d", &t);
for (int i = 0; i < t; i++)
{
int n;
scanf_s("%d", &n);
int flag = 1;
set<int> tmp;
for (int i = 1; i <= n; i++)
tmp.insert(i);
for (int i = 1; i <= n/2; i++)
{
scanf_s("%d", &num[i]);
tmp.erase(num[i]);
}
if (tmp.size() != n / 2)
{
printf("-1\n");
continue;
}
vector<int> res;
for (int i=n/2 ; i >= 1; i--)
{
auto p = tmp.lower_bound(num[i]);
if (p == tmp.begin())
{
flag = 0;
break;
}
int yh = *(--p);
res.insert(res.end(), { num[i],yh });
tmp.erase(p);
}
if (flag == 0)
{
printf("-1\n");
continue;
}
for (int i = n-1; i >= 0; i--)
{
printf("%d ", res[i]);
}
printf("\n");
}
}