链表是一种用于存储数据的数据结构,通过如链条一般的指针来连接元素
它的特点是插入与删除数据十分方便,但寻找与读取数据的表现欠佳
链表和数组都可用于存储数据。与链表不同,数组将所有元素按次序依次存储。不同的存储结构令它们有了不同的优势:
。但也因为这样,寻找、读取数据的效率不如数组高,在随机访问数据中的操作次数是
。但删除、插入的操作次数是 O(n) 次
双向链表的指针实现方式:
struct Node
{
int value; // data
Node *prev, *next; // pointers
};
Node *head, *tail;
void initialize() // create an empty list
{
head = new Node();
tail = new Node();
head->next = tail;
tail->prev = head;
}
void insert(Node *p, int value) // insert data after p
{
q = new Node();
q->value = value;
p->next->prev = q; q->next = p->next;
p->next = q; q->prev = p;
}
void remove(Node *p) // remove p
{
p->prev->next = p->next;
p->next->prev = p->prev;
delete p;
}
void recycle() // release memory
{
while (head != tail)
{
head = head->next;
delete head->prev;
}
delete tail;
}
双向链表的静态数组实现方式:
struct Node
{
int value;
int prev, next;
} node[SIZE];
int head, tail, tot;
void initialize()
{
tot = 2;
head = 1, tail = 2;
node[head].next = tail;
node[tail].prev = head;
}
int insert(int p, int value)
{
int q = ++ tot;
node[q].value = value;
node[node[p].next].prev = q;
node[q].next = node[p].next;
node[p].next = q; node[q].prev = p;
return q;
}
void remove(int p)
{
node[node[p].prev].next = node[p].next;
node[node[p].next].prev = node[p].prev;
}
void clear()
{
memset(node, 0, sizeof(node));
head = tail = tot = 0;
}
邻接表一般实现使用一个 vector<int>
来存每一个点的出边
竞赛里常用的是 链式前向星 存图方式,即数组模拟邻接表
int h[N], e[N], w[N], ne[N], idx;
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
// 邻接表:访问从x出发的所有边
for (int i = h[x]; ~i; i = ne[i])
{
int y = e[i], z = w[i];
// 一条有向边(x, y),权值为z
}
给定一个长度为
的序列
,
中的数各不相同。
对于
中的每一个数
,求:
以及令上式取到最小值的
(记为
)。若最小值点不唯一,则选择使
较小的那个。
输入格式
第一行输入整数
,代表序列长度。
第二行输入
个整数
,代表序列的具体数值,数值之间用空格隔开。
输出格式
输出共
行,每行输出两个整数,数值之间用空格隔开。
分别表示当
取
时,对应的
和
的值。
数据范围
输入样例:
3
1 5 3
输出样例:
4 1
2 1
维护这种类似问题的数据结构太多了,可以上线段树、树状数组、平衡树,但是本题的链表解法非常的巧妙,值得一写
链表解法是一种离线做法,步骤如下:
将原数组带着下标一起,按照元素的值从小到大顺排,然后以此顺序建立双向链表
找到原数组中下标为
的元素在双向链表中的位置
则
,欲使
最小,显然
必然在顺排后的新数组中与
相邻
因此直接找
的 前驱 和 后继 的最小值即是
的最小值
然后在双向链表中删去
,接着处理原数组中第
个数
删去的原因是,前缀中的邻值不包含大于当前下标的元素
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i ++ )
pos[a[i].y] = insert(node[tail].prev, a[i].x, a[i].y);
for (int i = n; i > 1; i -- )
{
int s = 2e9, idx = -1;
Node &t = node[pos[i]];
if (t.prev != head && s > abs(t.value - node[t.prev].value))
{
s = abs(t.value - node[t.prev].value);
idx = node[t.prev].pos;
}
if (t.next != tail && s > abs(t.value - node[t.next].value))
{
s = abs(t.value - node[t.next].value);
idx = node[t.next].pos;
}
res[i] = {s, idx};
remove(pos[i]);
}
依次读入一个整数序列,每当已经读入的整数个数为奇数时,输出已读入的整数构成的序列的中位数。
输入格式
第一行输入一个整数
,代表后面数据集的个数,接下来若干行输入各个数据集。
每个数据集的第一行首先输入一个代表数据集的编号的整数。
然后输入一个整数
,代表数据集中包含数据的个数,
一定为奇数,数据之间用空格隔开。
数据集的剩余行由数据集的数据构成,每行包含
个数据,最后一行数据量可能少于
个,数据之间用空格隔开。
输出格式
对于每个数据集,第一行输出两个整数,分别代表数据集的编号以及输出中位数的个数(应为数据个数加一的二分之一),数据之间用空格隔开。
数据集的剩余行由输出的中位数构成,每行包含
个数据,最后一行数据量可能少于
个,数据之间用空格隔开。
输出中不应该存在空行。
数据范围
,
, 所有
相加之和不超过
。
输入样例:
3
1 9
1 2 3 4 5 6 7 8 9
2 9
9 8 7 6 5 4 3 2 1
3 23
23 41 13 22 -3 24 -31 -11 -8 -7
3 5 103 211 -311 -45 -67 -73 -81 -99
-33 24 56
输出样例:
1 5
1 2 3 4 5
2 5
9 8 7 6 5
3 12
23 23 22 22 13 3 5 5 3 -3
-7 -3
对顶堆的做法在之前排序章节讲过了,说一下链表做法
同上一题一样是离线做法,同时维护数组内元素的值和原始下标,然后将数组按元素值从小到大排序
然后按照当前顺排顺序建立双向链表,显然对于
个数来说,中位数位于
的位置
将指针移动到该位置,便是第
轮的中位数答案,记录下该答案并保留指针位置,接着要分类讨论回滚到前一轮
最终输出所有答案即可,离线回滚真好玩(bushi)
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i ++ )
pos[a[i].y] = insert(node[tail].prev, a[i].x, a[i].y);
node[head].value = -INF, node[tail].value = INF;
int midx = head;
for (int i = 1; i <= n + 1 >> 1; i ++ ) midx = node[midx].next;
for (int i = n; i; i -- )
{
res[i] = node[midx].value;
Node &t = node[pos[i]];
if (t.pos == node[midx].pos) //删掉的是中位数
{
if (i & 1) midx = node[midx].prev;
else midx = node[midx].next;
}
else
{
if (i & 1 && pos[i] > midx) midx = node[midx].prev;
else if (i & 1 ^ 1 && pos[i] < midx) midx = node[midx].next;
}
remove(pos[i]);
}