题解 P1090 【合并果子】

Way_How_Fri3nd · 2018-06-22 09:22:10 · 题解

首先看到各位大佬用的都是堆或桶我也就放心了

当然我做这道题的思路也是堆

但是,简单的介绍堆并不是我写这道题的目的

我写这篇题解，是为了让各位了解一下大家平时很少注意的C++的某个方面

发掘更多新玩法

把你们从算法的深渊拉出来

—————————————分割线———————————————

————————————正文开始———————————————

————————————此篇为C++福利——————————

第一部分

设想一下，某一天，当你兴致勃勃的在洛谷里刷题时，看到了一道叫“合并果子”的题，你不屑地扫了一遍题目，心想着这种模板题也好意思入选提高组。迅速用小根堆将它AC后，却对堆产生了浓厚兴趣，便又找来一道与堆有关的题，惊讶发现该题的数据long long装不下，于是又写了一篇高精，但是在结合两者时却死活都结合不了，最后关掉电脑，生无可恋。

换一个场景，很多人都用过，至少接触过C++的STL库，那么应该就很熟悉形似这样的东西

priority_queue < int, vector<int>, greater<int> >;
vector < long long >;
queue <double >;

一些细心的人可能就会发现，在<>简直可以装下任何数据类型，那么C++，到底是如何实现这种操作的呢？

—————————分割线——————————

—————————分割线——————————

—————————分割线——————————

第二部分

我们回到第一个设想，你在写了一篇堆模板后，为了让它能够支持不同数据类型，对代码进行了这样的改动

typedef item int;
class heap{
    private:
        item h[1001];
        int len;
    public:
        heap();
        void push(item const &);
        void pop();
}

这样就可以针对不同数据类型，运用不同的堆

typedef item long long;
class heap{
    private:
        item h[1001];
        int len;
    public:
        heap();
        void push(item const &);
        void pop();
}

typedef item string;
class heap{
    private:
        item h[1001];
        int len;
    public:
        heap();
        void push(item const &);
        void pop();
}

但这样却有两个致命的缺陷，那就是每次使用，都得改一下头文件，并且不能同时存在两个不同类型的堆。那么应该怎样做呢？你不禁陷入了沉思。

第三部分

聪明的你当然知道如何使用网络来使自己的生活更加便利，于是你在“百度一下”中打出了

priority_queue < int, vector<int>, greater<int> >

并按下了回车，结果跳出来满屏的“容器”啊，“CSDN博客”啊之类的，让你心烦意燥，分分钟原地爆炸。或是瞅着顺眼的点了一篇，耐着性子看完，最后学到了NOTHING。

但是，一个词语突然从你眼前闪过，这个词语仿佛有着魔力，使你的视线一下子聚焦在了它身上，你的脑中仿佛浮现出了什么，又仿佛没有。

“类模板”

你轻轻地念叨着这词。

第四部分

类模板，模板的类型参数由关键字class 或关键字typename 及其后的标识符构成。在模板参数表中关键字class 和typename 的意义相同。(在标准C++之前关键字typename 没有被支持 ，把这个关键字加入到C++中的原因是因为有时必须要靠它来指导编译器解释模板定义。)，是对一批仅仅成员数据类型不同的类的抽象，程序员只要为这一批类所组成的整个类家族创建一个类模板，给出一套程序代码，就可以用来生成多种具体的类，(这类可以看作是类模板的实例)，从而大大提高编程的效率。————360百科

我们举个列子：

template<typename item>
class smallest_heap{
    private:
        item heap[10001];
        int len;
    public:
        smallest_heap();
        void push(item const &);
        void pop();
        item top();
        int size();
        bool empty();

};

其中第一排的

template<typename item>

就是关键，它指出接下来声明的某个类是模板，也就是部分数据类型不确定，暂且将这种数据类型叫做

item

而方法（也就是成员函数），相信各位大佬都会写。但是，要注意，在操作时，有一些不同指出

template<typename item>
smallest_heap<item>::smallest_heap(){
    len=0;
    memset(heap,0,sizeof(heap));
}

template<typename item>
void smallest_heap<item>::push(item const &n){
    heap[++len]=n;
    int son=len,father=son/2;
    while(heap[son]<heap[father] && father>=1){
        swap(heap[son],heap[father]);
        son=father,father=son/2;
    }
}

template<typename item>
void smallest_heap<item>::pop(){
    swap(heap[1],heap[len]);
    heap[len--]=0;
    int father=1,son=2;
    while(son<=len){
        if(son<len && heap[son]>heap[son+1]) son++;
        if(heap[father]>heap[son]){
            swap(heap[father],heap[son]);
            father=son,son=father*2;
        }else break;
    }
}

template<typename item>
item smallest_heap<item>::top(){
    return heap[1];
}

template<typename item>
int smallest_heap<item>::size(){
    return len;
}

template<typename item>
bool smallest_heap<item>::empty(){
    return len;
}

在每个方法前，都加了一排

template<typename item>

这是因为类的数据类型不确定，自然方法数据类型也不确定，所以用

item

来替代。并且在声明方法所属域时，也不是

smallest_heap::smallest_heap()

而是

smallest_heap<item>::smallest_heap()

最后送上AC代码以及小根堆，大根堆模板一份

番外

AC代码

#include<iostream>
#include<cstring>
using namespace std;

template<typename item>
class smallest_heap{
    private:
        item heap[10001];
        int len;
    public:
        smallest_heap();
        void push(item const &);
        void pop();
        item top();
        int size();
        bool empty();

};

template<typename item>
smallest_heap<item>::smallest_heap(){
    len=0;
    memset(heap,0,sizeof(heap));
}

template<typename item>
void smallest_heap<item>::push(item const &n){
    heap[++len]=n;
    int son=len,father=son/2;
    while(heap[son]<heap[father] && father>=1){
        swap(heap[son],heap[father]);
        son=father,father=son/2;
    }
}

template<typename item>
void smallest_heap<item>::pop(){
    swap(heap[1],heap[len]);
    heap[len--]=0;
    int father=1,son=2;
    while(son<=len){
        if(son<len && heap[son]>heap[son+1]) son++;
        if(heap[father]>heap[son]){
            swap(heap[father],heap[son]);
            father=son,son=father*2;
        }else break;
    }
}

template<typename item>
item smallest_heap<item>::top(){
    return heap[1];
}

template<typename item>
int smallest_heap<item>::size(){
    return len;
}

template<typename item>
bool smallest_heap<item>::empty(){
    return len;
}

smallest_heap<int> h;
int n,ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int a;
        cin>>a;
        h.push(a);
    }
    while(h.size()>1){
        int x=h.top(); h.pop();
        int y=h.top(); h.pop();
        h.push(x+y);
        ans+=x+y;
    }
    cout<<ans;
    return 0;
}

小根堆

#include<cstring>

template<typename item>
class smallest_heap{
    private:
        item heap[10001];
        int len;
    public:
        smallest_heap();
        void push(item const &);
        void pop();
        item top();
        int size();
        bool empty();

};

template<typename item>
smallest_heap<item>::smallest_heap(){
    len=0;
    memset(heap,0,sizeof(heap));
}

template<typename item>
void smallest_heap<item>::push(item const &n){
    heap[++len]=n;
    int son=len,father=son/2;
    while(heap[son]<heap[father] && father>=1){
        swap(heap[son],heap[father]);
        son=father,father=son/2;
    }
}

template<typename item>
void smallest_heap<item>::pop(){
    swap(heap[1],heap[len]);
    heap[len--]=0;
    int father=1,son=2;
    while(son<=len){
        if(son<len && heap[son]>heap[son+1]) son++;
        if(heap[father]>heap[son]){
            swap(heap[father],heap[son]);
            father=son,son=father*2;
        }else break;
    }
}

template<typename item>
item smallest_heap<item>::top(){
    return heap[1];
}

template<typename item>
int smallest_heap<item>::size(){
    return len;
}

template<typename item>
bool smallest_heap<item>::empty(){
    return len;
}

大根堆

#include<cstring>

template<typename item>
class largest_heap{
    private:
        item heap[10001];
        int len;
    public:
        largest_heap();
        void push(item const &);
        void pop();
        item top();
        int size();
        bool empty();

};

template<typename item>
largest_heap<item>::largest_heap(){
    len=0;
    memset(heap,0,sizeof(heap));
}

template<typename item>
void largest_heap<item>::push(item const &n){
    heap[++len]=n;
    int son=len,father=son/2;
    while(heap[son]>heap[father] && father>=1){
        swap(heap[son],heap[father]);
        son=father,father=son/2;
    }
}

template<typename item>
void largest_heap<item>::pop(){
    swap(heap[1],heap[len]);
    heap[len--]=0;
    int father=1,son=2;
    while(son<=len){
        if(son<len && heap[son]<heap[son+1]) son++;
        if(heap[father]<heap[son]){
            swap(heap[father],heap[son]);
            father=son,son=father*2;
        }else break;
    }
}

template<typename item>
item largest_heap<item>::top(){
    return heap[1];
}

template<typename item>
int largest_heap<item>::size(){
    return len;
}

template<typename item>
bool largest_heap<item>::empty(){
    return len;

同时也可以支持自己编写的类，但须提供“<”或“>”的运算符重载，例如

class T{
    private:
        int a;
    public:
        bool operator<(T const &type){
            return a<type.a;
        }
};
smallest_heap<T> heap;

最后的总结

我们现在所运用的C++，只是它的冰山一角，如果有与我同样爱好C++的，对运算符重载，lambda函数，类继承，函数重载，虚方法等感兴趣的，可以私信我，一起进步！

番外中的番外

推荐一个网站和一本书

C语言中文网 c.biancheng.net

《C++ Primer Plus》

            ----毕竟萌新，文笔不好，请多多包容