算法分析:
这题一开始我愚蠢了……WA了一发……
题目说,他有一根完整的,长度是所需N块模板的长度之和的长木板,然后要你去切割,每次切割会消耗总长的长度那么多的能量,问你怎么搞耗能最少??这题一看很明显,每次切割耗能都是被切割的长度那么多,所以,当然是长痛不如短痛,一次性多切一点为好,难道这题是排序?我们不妨来模拟这个过程:
第一次切割:当然切最大的,也就是8
L = 21
耗能ans = 21
切完后:
L = 13
第二次切割:当然还是切当然最大的,也还是8
L = 13
耗能ans = 21 + 13 = 34
L = 5(此时已经完工,无需再切)
分析这个过程,貌似确实很容易被误解成排序+贪心……
那么这个排序+贪心错在了哪里呢?
从原始模板逐渐去切割,其实不是对的!因为一次不一定只可以切一块模板,只要是你手里有的模板都可以同时去切割,消耗的能量是它们这些模板的总和!!
那么正解是什么呢?
既然我们一次可能不止切一块木板,也就是说,可能有很多分支并线进行!于是我们应该从切割的结果开始向上溯源,也就是和合并果子那题差不多了!每次都是把一个长木板切成两个小木板,反过来看就是把两个子节点合并,之和便是它们的父节点!我们的目的是让每个合并后的父节点之和最小,那么就是要形成小顶堆,小顶堆代码如下不解释:
小顶堆的解决方案:
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
int main(){
priority_queue<int, vector<int>, greater<int> > q;
int n, a;
long long ans = 0;
scanf("%d", &n);
while(n--){
scanf("%d", &a);
q.push(a);
}
while((int)q.size() > 1){
int u = q.top(); q.pop();
int v = q.top(); q.pop();
ans += (u + v);
q.push(u + v);
}
printf("%d", ans);
return 0;
}
第二题:
算法分析:
这题一看就是要动态维护中位数!我们可以看到,这个输出的要求是前1 3 5 7……个数的中位数,这个要求说明,中位数也是输入的一个数,不会出现那种,前偶数个数的中位数,需要求平均值的情况!
所谓中位数,我们可以把输入的n个数分成两堆,一堆存放较大数,一堆存放较小数,由于是前奇数个的中位数,于是这两个堆应该是一个堆比另一个堆的规模大1(且只能大1!!)那么这个中位数如何得到呢?中位数一定是:
较大数所在堆的最小数
较小数所在堆的最大数
于是这个较大数,就应该放在一个小根堆的数据结构、较小数,就应该放在一个大根堆的数据结构!
然后每次输入的时候,首先判断是否比小根堆的最小数大,如果大则放入小根堆,否则放入大根堆。并且我们还要维护堆的规模的性质!如果出现了某个堆的规模比另一个堆的规模大的超过1,就把这个堆的堆顶取出来放入另一个堆,因为这样放才不会影响我们大、小数所在堆的性质!
堆动态维护中位数,我的解决方案:
#include <iostream>
#include <queue>
using namespace std;
int main(){
priority_queue<int> q1;
priority_queue<int, vector<int>, greater<int> > q2;
int n, a;
cin >> n;
for(int i = 1;i <= n;++i){
cin >> a;
if(q2.empty() || a > q2.top())
q2.push(a);
else
q1.push(a);
if((int)q1.size() - (int)q2.size() > 1){
int u = q1.top();
q1.pop();
q2.push(u);
}
if((int)q2.size() - (int)q1.size() > 1){
int u = q2.top();
q2.pop();
q1.push(u);
}
if(i & 1){
int res = (int)q1.size() > (int)q2.size() ? q1.top() : q2.top();
cout << res << endl;
}
}
return 0;
}
第三题:
算法分析:
还是再仔细读读这个操作:
首先要注意:
合并堆是合并第x个数所在的堆 和 第y个数所在的堆 ,所以我们需要查堆顶,怎么查?
然后要注意:
还需要判断每个数是否已经被删除,以及是否在一个堆中,怎么处理?
其实这些问题还是蛮容易的,判断是否在一个堆中以及查堆顶,都很容易想到用并查集的查询方式,路径压缩找根!然后判断每个数是否被删除,那就给每个节点设置一个bool类型的visit变量即可!
然后剩下的,就是普通的可并堆 的算法问题!什么是可并堆?我只会一种可并堆,那就是左式堆
讲解左式堆:
两个堆合并,假设一个堆的规模是n,另一个堆的规模是m,如果采用朴素的插入→自顶向下的下滤,那么需要的开销是:O(n * log(n)+ m * log(n))这个复杂度来由我就不解释了,不懂可私信我,如果采用Floyd思想,采用朴素的插入→自底向上的下滤,需要的开销是:O(m + n),这个是因为自底向上,复杂度取决于高度之和,一颗完全二叉树(左式堆的基本结构)高度为1的节点,也就是叶子节点占n/2,然后逐层往上,高度最高的节点便是根节点,只存在一个,也就是说,高度高的节点是很少的,于是Floyd思想的下滤就开销很少了(其实这个思想说白了就是一种小堆叠成大堆的思想)。然后左式堆的思想就更牛逼了,单独搞一段来讲解:
左式堆有一个参数:npl(null path length)也就是空节点路径长度,我们设空节点的长度为0,其他的节点x的npl有公式:npl(x) = 1 + Min( npl(x.Lchild) , npl(x.Rchild) ),然后我们的左式堆就要维护左偏性+堆序性,所谓左偏就是始终要左子树的npl大于右子树!这样的化,根节点向下下滤,最长的路径便是右侧链,这个右侧链的高度,是根节点的最大满二叉子树的高度,便是log(n),于是左式堆的插入开销就是:O(log(n))就比前面的算法都要优秀很多很多!!!
左式堆的解决方案:
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 5;
struct LeftHeapNode
{
LeftHeapNode* rc, * lc, * rt;
int val, npl, vis, id;
};
LeftHeapNode* Node[maxn];
int n, m, x, y;
LeftHeapNode* find(LeftHeapNode* p)
{
while (p->rt)
p = p->rt;
return p;
}
LeftHeapNode* mergeTop(LeftHeapNode* x, LeftHeapNode* y)
{
if (!x) return y;
if (!y) return x;
if (x->val > y->val || (x->val == y->val && x->id > y->id))
swap(x, y);
x->rc = mergeTop(x->rc, y);
x->rc->rt = x;
if (!x->lc || x->lc->npl < x->rc->npl)
swap(x->lc, x->rc);
if (!x->rc)
x->npl = 0;
else
x->npl = x->rc->npl + 1;
return x;
}
int main()
{
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i)
{
int val;
scanf("%d", &val);
Node[i] = new LeftHeapNode;
Node[i]->val = val;
Node[i]->lc = Node[i]->rc = Node[i]->rt = NULL;
Node[i]->id = i;
Node[i]->npl = 0;
Node[i]->vis = 0;
}
while (m--)
{
int op;
scanf("%d", &op);
if (1 == op)
{
int x, y;
scanf("%d %d", &x, &y);
if (Node[x]->vis || Node[y]->vis)
continue;
LeftHeapNode* fx = find(Node[x]);
LeftHeapNode* fy = find(Node[y]);
if (fx != fy)
mergeTop(fx, fy);
}
else
{
int x;
scanf("%d", &x);
if (Node[x]->vis)
{
printf("-1\n");
continue;
}
LeftHeapNode* fx = find(Node[x]);
printf("%d\n", fx->val);
fx->vis = 1;
LeftHeapNode* L = fx->lc;
LeftHeapNode* R = fx->rc;
if (L) L->rt = NULL;
if (R) R->rt = NULL;
fx->lc = fx->rc = NULL;
mergeTop(L, R);
delete fx;
}
}
return 0;
}
详解左式堆操作:
首先是最重要的合并
左式堆的合并发生在右侧链,以每次处理都维护堆序性和左偏性闻名!而可能会破坏左偏性和堆序性的地方就出现在:合并、删除(其实删除也是合并,稍后讲!)
两堆合并,其实是个递归的过程,因为右侧链的子树也有右侧链,要递归到右侧链只有一个节点的时候,才真正发生链接操作!
LeftHeapNode* mergeTop(LeftHeapNode* x, LeftHeapNode* y)
{
if (!x) return y;
if (!y) return x;
if (x->val > y->val || (x->val == y->val && x->id > y->id))
swap(x, y);
x->rc = mergeTop(x->rc, y);
x->rc->rt = x;
if (!x->lc || x->lc->npl < x->rc->npl)
swap(x->lc, x->rc);
if (!x->rc)
x->npl = 0;
else
x->npl = x->rc->npl + 1;
return x;
}
这是合并的代码,递归基就不说了,
第一步先判断堆序性是否会被破坏,如果可能会被破坏,就交换节点,保证堆序性不破坏
if (x->val > y->val || (x->val == y->val && x->id > y->id))
swap(x, y);
然后是关键的递归:
x->rc = mergeTop(x->rc, y);
每次都去找右侧链,把以 y 为顶的堆放到右侧链上去,递归完成之后会向上跑到根节点的右子节点处,然后要重新把右子节点链回父节点,这不是递归能做到的,需要手动完成:
x->rc->rt = x;
现在合并工作完成了,但是还需要善后,因为左偏性可能被破坏,于是判断左偏性,如果破坏了就需要交换左右子树,去维护左偏性:
if (!x->lc || x->lc->npl < x->rc->npl)
swap(x->lc, x->rc);
左偏性完成了之和,就需要更新根节点的npl值,因为可能有新的右子树,右子树的npl值变了则根节点的npl值也要跟着变!这时候需要判断,如果右子树为空,就不能去访问人家的npl,否则空指针访问会抛出异常的!
if (!x->rc)
x->npl = 0;
else
x->npl = x->rc->npl + 1;
这里和《c++数据结构 邓俊辉版》的说法有点区别,这里我们规定叶子节点的(或者在左偏性下,右子树为空的)的节点,npl = 0,其他的很显然,不用多说。
这样就完成了合并操作!
然后讲讲删除操作:
LeftHeapNode* pop(LeftHeapNode* x)
{
LeftHeapNode* L = x->lc;
LeftHeapNode* R = x->rc;
if (L) L->rt = NULL;
if (R) R->rt = NULL;
x->lc = x->rc = NULL;
return merge(L, R);
/* 错误的解决方案
if (x->lc) x->lc->rt = NULL;
if (x->rc) x->rc->rt = NULL;
return merge(x->lc, x->rc);// 会导致空指针访问!
*/
}
其实删除也是合并,这里我就只讲一下删除的思想,删除其实就是把被删除节点的左右子树合并的操作。但是重点是要妥善处理好善后的工作!!!千万不能造成空指针访问!!!
第四题:算法分析:
这题和上题没啥大区别啊!一开始,各自为政,然后俩猴子打架,牛逼的做老大。这不就是大顶堆吗?然后俩猴群(俩堆)对垒,就会派出堆的最屌的猴子(也就是堆顶)去干架,然后干完俩猴子就亲密无间,成为一个堆的猴子了(不打不相识?)但是值得注意的是:
猴子都有一个强值,经过决斗后,强值会减少到原来的一半(即10减为5,5减为2)。
这也就意味着,堆序性可能需要重新维护!这就是和上题不一样的地方!这个如何处理呢??
每次干架前,我都可以把需要干起来的猴王(堆顶),先减半,减半再放入原堆,然后俩堆再合并 ,就解决这个问题了!!
此题的解决方案:
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 5;
struct LeftHeapNode
{
LeftHeapNode* lc, * rc, * rt;
int val, npl;
~LeftHeapNode() { delete lc; delete rc; delete rt; }
};
LeftHeapNode* Node[maxn];
LeftHeapNode* find(LeftHeapNode* x)
{
while (x->rt)
x = x->rt;
return x;
}
LeftHeapNode* merge(LeftHeapNode* x, LeftHeapNode* y)
{
if (!x) return y;
if (!y) return x;
if (x->val < y->val)
swap(x, y);
x->rc = merge(x->rc, y);
x->rc->rt = x;
if (!x->lc || x->lc->npl < x->rc->npl)
swap(x->lc, x->rc);
if (!x->rc)
x->npl = 0;
else
x->npl = 1 + x->rc->npl;
return x;
}
LeftHeapNode* pop(LeftHeapNode* x)
{
LeftHeapNode* L = x->lc;
LeftHeapNode* R = x->rc;
if (L) L->rt = NULL;
if (R) R->rt = NULL;
x->lc = x->rc = NULL;
return merge(L, R);
/* 错误的解决方案
if (x->lc) x->lc->rt = NULL;
if (x->rc) x->rc->rt = NULL;
return merge(x->lc, x->rc);// 会导致空指针访问!
*/
}
int main()
{
int n, m;
while (~scanf("%d", &n))
{
for (int i = 1; i <= n; ++i)
{
int val;
scanf("%d", &val);
Node[i] = new LeftHeapNode;
Node[i]->lc = Node[i]->rc = Node[i]->rt = NULL;
Node[i]->val = val;
Node[i]->npl = 0;
}
scanf("%d", &m);
while (m--)
{
int x, y;
scanf("%d %d", &x, &y);
LeftHeapNode* fx = find(Node[x]);
LeftHeapNode* fy = find(Node[y]);
if (fx == fy)
printf("-1\n");
else
{
fx->val >>= 1;
fy->val >>= 1;
LeftHeapNode* newL = pop(fx);
LeftHeapNode* newR = pop(fy);
newL = merge(fx, newL);
newR = merge(fy, newR);
newL = merge(newL, newR);
printf("%d\n", newL->val);
}
}
}
return 0;
}