题解 P1090 【合并果子】
Way_How_Fri3nd
2018-06-22 09:22:10
## 首先看到各位大佬用的都是堆或桶我也就放心了
~~当然我做这道题的思路也是堆~~
但是,简单的介绍堆并不是我写这道题的目的
# 我写这篇题解，是为了让各位了解一下大家平时很少注意的C++的某个方面
~~发掘更多新玩法~~
~~把你们从算法的深渊拉出来~~
—————————————分割线———————————————
————————————正文开始———————————————
————————————此篇为C++福利——————————
## 第一部分
设想一下，某一天，当你兴致勃勃的在洛谷里刷题时，看到了一道叫“合并果子”的题，你不屑地扫了一遍题目，心想着这种模板题也好意思入选提高组。迅速用小根堆将它AC后，却对堆产生了浓厚兴趣，便又找来一道与堆有关的题，惊讶发现该题的数据long long装不下，于是又写了一篇高精，但是在结合两者时却死活都结合不了，最后关掉电脑，生无可恋。
换一个场景，很多人都用过，至少接触过C++的STL库，那么应该就很熟悉形似这样的东西
```cpp
priority_queue < int, vector<int>, greater<int> >;
vector < long long >;
queue <double >;
```
一些细心的人可能就会发现，在<>简直可以装下任何数据类型，那么C++，到底是如何实现这种操作的呢？
—————————分割线——————————
—————————分割线——————————
—————————分割线——————————
## 第二部分
我们回到第一个设想，你在写了一篇堆模板后，为了让它能够支持不同数据类型，对代码进行了这样的改动
```cpp
typedef item int;
class heap{
private:
item h[1001];
int len;
public:
heap();
void push(item const &);
void pop();
}
```
这样就可以针对不同数据类型，运用不同的堆
```cpp
typedef item long long;
class heap{
private:
item h[1001];
int len;
public:
heap();
void push(item const &);
void pop();
}
```
```cpp
typedef item string;
class heap{
private:
item h[1001];
int len;
public:
heap();
void push(item const &);
void pop();
}
```
但这样却有两个致命的缺陷，那就是每次使用，都得改一下头文件，并且不能同时存在两个不同类型的堆。那么应该怎样做呢？你不禁陷入了沉思。
## 第三部分
聪明的你当然知道如何使用网络来使自己的生活更加便利，于是你在“百度一下”中打出了
```cpp
priority_queue < int, vector<int>, greater<int> >
```
并按下了回车，结果跳出来满屏的“容器”啊，“CSDN博客”啊之类的，让你心烦意燥，分分钟原地爆炸。或是瞅着顺眼的点了一篇，耐着性子看完，最后学到了NOTHING。
但是，一个词语突然从你眼前闪过，这个词语仿佛有着魔力，使你的视线一下子聚焦在了它身上，你的脑中仿佛浮现出了什么，又仿佛没有。
### “类模板”
你轻轻地念叨着这词。
## 第四部分
### 类模板，模板的类型参数由关键字class 或关键字typename 及其后的标识符构成。在模板参数表中关键字class 和typename 的意义相同。(在标准C++之前关键字typename 没有被支持 ，把这个关键字加入到C++中的原因是因为有时必须要靠它来指导编译器解释模板定义。)，是对一批仅仅成员数据类型不同的类的抽象，程序员只要为这一批类所组成的整个类家族创建一个类模板，给出一套程序代码，就可以用来生成多种具体的类，(这类可以看作是类模板的实例)，从而大大提高编程的效率。————360百科
我们举个列子：
```cpp
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();
};
```
其中第一排的
```cpp
template<typename item>
```
就是关键，它指出接下来声明的某个类是模板，也就是部分数据类型不确定，暂且将这种数据类型叫做
```cpp
item
```
而方法（也就是成员函数），相信各位大佬都会写。但是，要注意，在操作时，有一些不同指出
```cpp
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;
}
```
在每个方法前，都加了一排
```cpp
template<typename item>
```
这是因为类的数据类型不确定，自然方法数据类型也不确定，所以用
```cpp
item
```
来替代。并且在声明方法所属域时，也不是
```cpp
smallest_heap::smallest_heap()
```
而是
```cpp
smallest_heap<item>::smallest_heap()
```
最后送上AC代码以及小根堆，大根堆模板一份
## 番外
AC代码
```cpp
#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;
}
```
小根堆
```cpp
#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;
}
```
大根堆
```cpp
#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;
```
同时也可以支持自己编写的类，但须提供“<”或“>”的运算符重载，例如
```cpp
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》
----毕竟萌新，文笔不好，请多多包容