# 14012: 【原4012】合并果子

### 题目描述

author: noip2004 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4012

## Sample Input

``````3
1 2 9
``````

## Sample Output

``````15
``````

## BugenZhao's solution

``````//
// Created by BugenZhao on 2019/5/8.
//

//
// Created by BugenZhao on 2019/4/5.
//

#ifndef SBL_BPRIORITYQUEUE_H
#define SBL_BPRIORITYQUEUE_H

namespace bpq {
template<typename Item>
struct greater {
bool operator()(const Item &a, const Item &b) {
return a > b;
}
};

template<typename Item>
struct less {
bool operator()(const Item &a, const Item &b) {
return a < b;
}
};
}

template<typename Item, typename Comparator = bpq::greater<Item>>
class BPriorityQueue {
Comparator comparator;
Item *pq;
int N = 0;
int maxN;
int minN;

private:
bool cmp(int i, int j) {
return comparator(pq[i], pq[j]);
}

void exch(int i, int j) {
Item item = pq[i];
pq[i] = pq[j];
pq[j] = item;
}

void resize(int newMaxN) {
Item *old = pq;
pq = new Item[newMaxN + 1];
int length = newMaxN > maxN ? maxN : newMaxN;
for (int i = 1; i <= length; ++i) {
pq[i] = old[i];
}
delete[] old;
}

void swim(int k) {
while (k > 1 && cmp(k, k / 2)) {
exch(k / 2, k);
k /= 2;
}
}

void sink(int k) {
int j;
while (2 * k <= N) {
j = 2 * k;
j += (j < N && cmp(j + 1, j));
if (cmp(j, k)) {
exch(k, j);
k = j;
} else break;
}
}

public:
BPriorityQueue() {
this->maxN = 1;
this->minN = -1;
pq = new Item[1 + 1];
}

BPriorityQueue(int maxN) {
this->maxN = maxN;
this->minN = maxN;
pq = new Item[maxN + 1];
}

BPriorityQueue(const Item *pq, int size) {
maxN = N = size;
minN = N;
this->pq = new Item[size + 1];
for (int i = 1; i <= N; ++i) {
this->pq[i] = pq[i - 1];
}
for (int k = N / 2; k >= 1; --k) {
sink(k);
}
}

bool isEmpty() {
return N == 0;
}

int size() {
return N;
}

void insert(const Item &item) {
if (N == maxN)
resize(2 * N);
pq[++N] = item;
swim(N);
}

Item pop() {
if (N <= maxN / 4) {
if (maxN / 2 >= minN) resize(maxN / 2);
else resize(minN);
}
Item item = pq[1];
exch(1, N);
--N;
sink(1);
return item;
}

const Item &peek() {
return pq[1];
}

virtual ~BPriorityQueue() {
delete[] pq;
}
};

#endif //SBL_BPRIORITYQUEUE_H

#include <iostream>
#include <string>

using std::ios, std::cin, std::cout, std::endl, std::string;
using ll = long long;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
int tmp;
BPriorityQueue<int, bpq::less<int>> pq(n);
for (int i = 0; i < n; ++i) {
cin >> tmp;
pq.insert(tmp);
}

int a, b;
int ans = 0;
while (pq.size() >= 2) {
a = pq.pop();
b = pq.pop();
pq.insert(a + b);
ans += a + b;
}

cout << ans << endl;
return 0;
}
``````

## ligongzzz's solution

``````#include "iostream"
using namespace std;

template <class T>
class mVector {
T** vector_data = nullptr;
unsigned int size = 0;
unsigned int capacity = 0;

public:
//构造函数
mVector() = default;
mVector(unsigned int _size) :size(_size) {
capacity = _size * 2;
vector_data = new T * [capacity] {nullptr};
}
mVector(unsigned int _size, const T& val) :size(_size) {
capacity = _size * 2;
vector_data = new T * [capacity] {nullptr};
for (unsigned int i = 0; i < _size; ++i)
vector_data[i] = new T(val);
}
mVector(const mVector<T> & _vector) :size(_vector.size), capacity(_vector.capacity) {
vector_data = new T * [capacity] {nullptr};
for (int i = 0; i < size; ++i)
vector_data[i] = new T(*_vector.vector_data[i]);
}
//析构函数
~mVector() {
for (unsigned int i = 0; i < size; ++i)
delete vector_data[i];
delete[] vector_data;
}

//迭代器
class iterator {
T** pos = nullptr;
friend iterator mVector<T>::begin();
friend iterator mVector<T>::end();
friend void mVector<T>::erase(const iterator& val);
public:
iterator() = default;
iterator(const iterator& other) {
pos = other.pos;
}
iterator& operator++() {
++pos;
return *this;
}
iterator operator++(int) {
iterator temp(*this);
++pos;
return temp;
}
iterator& operator--() {
--pos;
return *this;
}
iterator operator--(int) {
iterator temp(*this);
--pos;
return temp;
}
bool operator==(const iterator& other) const {
return pos == other.pos;
}
bool operator!=(const iterator& other) const {
return pos != other.pos;
}
iterator& operator=(const iterator& other) {
pos = other.pos;
return *this;
}
T& operator*() const {
return **pos;
}
};

//增加元素
void push_back(const T & val) {
if (size < capacity)
vector_data[size++] = new T(val);
else {
T** temp_data = new T * [(capacity + 1) * 2]{ nullptr };
for (unsigned int i = 0; i < size; ++i)
temp_data[i] = vector_data[i];
temp_data[size++] = new T(val);
capacity = (capacity + 1) * 2;
delete[] vector_data;
vector_data = temp_data;
}
}

//删除末尾
void pop_back() {
delete vector_data[size];
vector_data[size--] = nullptr;
}

//清空
void clear() {
for (unsigned int i = 0; i < size; ++i) {
delete vector_data[i];
vector_data[i] = nullptr;
}
size = 0;
}

//删除
void erase(const iterator & val) {
delete* val.pos;
for (auto p = val.pos; p != vector_data + size - 1; ++p)
* p = *(p + 1);
--size;
vector_data[size] = nullptr;
}

//重载运算符
T & operator[](const unsigned int& pos) {
return *vector_data[pos];
}

iterator begin() {
iterator temp;
temp.pos = vector_data;
return temp;
}

iterator end() {
iterator temp;
temp.pos = vector_data + size;
return temp;
}

};

template <class T>
class myPriorityQueue {
public:
mVector<T> queueData;
unsigned int sizeOfQueue = 0;
bool(*cmp)(T a, T b) = [](T a, T b) {return a < b; };

//向下过滤
void percolateDown(unsigned int pos) {
while (pos * 2 <= sizeOfQueue) {
if (pos * 2 + 1 > sizeOfQueue) {
//交换
if (cmp(queueData[pos * 2], queueData[pos])) {
auto temp = queueData[pos * 2];
queueData[pos * 2] = queueData[pos];
queueData[pos] = temp;
}
break;
}
else {
bool minNum = cmp(queueData[pos * 2 + 1], queueData[pos * 2]);
if (cmp(queueData[pos * 2 + minNum], queueData[pos])) {
auto temp = queueData[pos * 2 + minNum];
queueData[pos * 2 + minNum] = queueData[pos];
queueData[pos] = temp;
pos = pos * 2 + minNum;
}
else break;
}
}
}

//构建
myPriorityQueue() {
queueData.clear();
queueData.push_back((T)0);
sizeOfQueue = 0;
}

//compare函数返回父结点a与孩子结点b的关系正确与否
myPriorityQueue(bool(*compare)(T a, T b)) :cmp(compare) {
queueData.clear();
queueData.push_back(*new T);
sizeOfQueue = 0;
}

//根据数组建立堆
void buildHeap(T* eleData, unsigned int eleNum) {
queueData.clear();
sizeOfQueue = eleNum;
queueData.push_back(*new T);
for (unsigned int i = 1; i <= eleNum; i++)
queueData.push_back(eleData[i - 1]);
//向下过滤
for (unsigned int pos = eleNum / 2; pos > 0; pos--)
percolateDown(pos);
}

void refresh() {
//向下过滤
for (unsigned int pos = size() / 2; pos > 0; pos--)
percolateDown(pos);
}

//判断是否空
bool empty() {
return sizeOfQueue == 0;
}

//返回队列大小
auto size() {
return sizeOfQueue;
}

//入队
void push(const T & input) {
sizeOfQueue++;
queueData.push_back(input);

//向上过滤
for (auto i = sizeOfQueue; i > 1; i = i / 2) {
//判断是否比父结点更小
if (cmp(queueData[i], queueData[i / 2])) {
//交换
auto temp = queueData[i];
queueData[i] = queueData[i / 2];
queueData[i / 2] = temp;
}
else break;
}
}

//队列最前
T top() {
return queueData[1];
}

//出队
T pop() {
auto temp = queueData[1];
queueData[1] = queueData[sizeOfQueue--];
queueData.pop_back();
percolateDown(1);
return temp;
}
};

int weight[20000] = { 0 };

int main() {
//ios::sync_with_stdio(false);
//cin.tie(NULL);

int n;
cin >> n;

for (int i = 0; i < n; i++)
cin >> weight[i];

//排除特殊情况
if (n == 1) {
cout << weight[0];
return 0;
}

myPriorityQueue<int> fruit;
fruit.buildHeap(weight, n);

long long ans=0;
//不断循环
while (fruit.sizeOfQueue > 2) {
if (fruit.queueData[2] <= fruit.queueData[3]) {
fruit.queueData[2] += fruit.queueData[1];
ans += fruit.queueData[2];
fruit.percolateDown(2);
}
else {
fruit.queueData[3] += fruit.queueData[1];
ans += fruit.queueData[3];
fruit.percolateDown(3);
}
//剔除最小的元素
fruit.pop();
}
ans += fruit.queueData[1] + fruit.queueData[2];
cout << ans;
return 0;
}
``````

## Neight99's solution

``````#include <iostream>

using namespace std;

const int maxN = 1e5 + 100;

template <class Type>
class priorityQueue {
private:
int currentSize;
Type *array;
int maxSize;

void doubleSpace();
// void buildHeap();
void percolateDown(int);

public:
priorityQueue(int capacity = maxN);
// priorityQueue(const Type data[],int size);
~priorityQueue();
bool isEmpty() const;
void enQueue(const Type &x);
Type deQueue();
};

template <class Type>
priorityQueue<Type>::priorityQueue(int capacity)
: maxSize(capacity), currentSize(0) {
array = new Type[capacity];
}

template <class Type>
priorityQueue<Type>::~priorityQueue() {
delete[] array;
}

template <class Type>
bool priorityQueue<Type>::isEmpty() const {
return currentSize == 0;
}

template <class Type>
return array[1];
}

template <class Type>
void priorityQueue<Type>::enQueue(const Type &x) {
if (currentSize == maxSize - 1) {
doubleSpace();
}

int hole = ++currentSize;
for (; hole > 1 && x < array[hole / 2]; hole /= 2) {
array[hole] = array[hole / 2];
}

array[hole] = x;
}

template <class Type>
Type priorityQueue<Type>::deQueue() {
Type minItem;

minItem = array[1];
array[1] = array[currentSize--];
percolateDown(1);

return minItem;
}

template <class Type>
void priorityQueue<Type>::percolateDown(int hole) {
int child;
Type tmp = array[hole];

for (; hole * 2 <= currentSize; hole = child) {
child = hole * 2;

if (child != currentSize && array[child + 1] < array[child]) {
child++;
}

if (array[child] < tmp) {
array[hole] = array[child];
} else {
break;
}
}
array[hole] = tmp;
}

template <class Type>
void priorityQueue<Type>::doubleSpace() {
Type *tmp = array;

maxSize *= 2;

array = new Type[maxSize];
for (int i = 0; i < currentSize; i++) {
array[i] = tmp[i];
}

delete[] tmp;
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int N, tmp1, tmp2, tmp3;
long long strength = 0;
priorityQueue<int> fruits;

cin >> N;

for (int i = 0; i < N; i++) {
cin >> tmp1;
fruits.enQueue(tmp1);
}

for (int i = 0; i < N - 1; i++) {
tmp1 = fruits.deQueue();
tmp2 = fruits.deQueue();
tmp3 = tmp1 + tmp2;
fruits.enQueue(tmp3);
strength += tmp3;
}

cout << strength;
}
``````

## q4x3's solution

``````/**
* 最小堆 + 哈夫曼
* 每次把最小的两个取出来加到一起
* 加入ans
* 并放回堆中
**/
#include <iostream>
#include <stdio.h>

using namespace std;

long long int N, F[10233], ans;

void down(long long int rt, long long int size) {
long long int tmp = F[rt];
if((rt << 1) > size) return;
else if((rt << 1 | 1) > size) {
if(tmp > F[rt << 1]) {
F[rt] = F[rt << 1];
F[rt << 1] = tmp;
}
return;
} else {
long long int chi1 = F[rt << 1], chi2 = F[rt << 1 | 1];
if(chi1 < tmp && chi1 <= chi2) {
F[rt] = chi1;
F[rt << 1] = tmp;
down(rt << 1, size);
} else if(chi2 < tmp && chi2 <= chi1) {
F[rt] = chi2;
F[rt << 1 | 1] = tmp;
down(rt << 1 | 1, size);
}
}
}

void build() {
for(long long int i = N / 2;i > 0;-- i) {
down(i, N);
}
}

void op(long long int size) {
long long int head = F[1];
F[1] = F[size];
down(1, size - 1);
F[1] += head; ans += F[1];
down(1, size - 1);
}

int main() {
scanf("%lld", &N);
for(long long int i = 1;i <= N;++ i)
scanf("%lld", &F[i]);
build();
for(long long int i = 0;i < N - 1;++ i) {
op(N - i);
}
cout << ans << endl;
return 0;
}
``````

## skyzh's solution

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

#include <stdio.h>

template<typename T>
struct Heap {
T *data;
int cap, len;

Heap(int cap = 1024) : cap(cap + 1), len(0) {
data = new T[cap];
}

Heap(const Heap& that) : cap(that.cap), len(that.len) {
data = new T[cap];
memcpy(data, that.data, sizeof(T) * cap);
}

~Heap() { delete[] data; }

void push(const T &x) {
data[++len] = x;
swim(len);
}

T pop() {
swap(data[1], data[len--]);
sink(1);
return data[len + 1];
}

void top() {
return data[1];
}

bool less(int a, int b) {
if (a > len || b > len) return false;
return data[a] < data[b];
}

void swim(int idx) {
int _idx;
while (idx > 1 && less(idx, _idx = idx / 2)) {
swap(data[idx], data[_idx]);
idx = _idx;
}
}

void sink(int idx) {
int _idx;
while ((_idx = 2 * idx) <= len) {
if (_idx < len && less(_idx + 1, _idx)) _idx++;
if (less(idx, _idx)) break;
swap(data[idx], data[_idx]);
idx = _idx;
}
}

bool empty() {
return len == 0;
}
};

int main() {
int n;
int x[20000];
long long sum = 0;
Heap <int> heap(20000);
cin >> n;
int _data;
for (int i = 0; i < n; i++) {
cin >> _data;
heap.push(_data);
}
for (int i = 0; i < n - 1; i++) {
int op1 = heap.pop(), op2 = heap.pop();
int s = op1 + op2;
heap.push(s);
sum += s;
}
cout << sum << endl;
return 0;
}
``````

## victrid's solution

``````#include <iostream>
using namespace std;
long long strage[400005];
int treesize;
void swap(long long& a1, long long& a2) {
if (a1 != a2) {
a1 ^= a2;
a2 ^= a1;
a1 ^= a2;
}
return;
};
void insert(long long i) {
strage[++treesize] = i;
int x              = treesize;
while (x != 1) {
if (strage[x] < strage[x >> 1]) {
swap(strage[x], strage[x >> 1]);
x >>= 1;
} else
break;
}
return;
}
long long pop() {
swap(strage[1], strage[treesize]);
treesize--;
int i = 2;
while (i <= treesize) {
if ((i | 1) <= treesize && strage[i | 1] < strage[i])
i |= 1;
if (strage[i] < strage[i >> 1]) {
swap(strage[i], strage[i >> 1]);
i <<= 1;
} else
break;
}
return strage[treesize + 1];
}
int main() {
int n, x, y;
long long ans = 0;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &x);
insert(x);
}
while (treesize > 1) {
x = pop();
y = pop();
ans += x + y;
insert(x + y);
}
printf("%lld", ans);
return 0;
}
``````

## WashSwang's solution

``````#include <iostream>
#include <cstdio>
using namespace std;
int rmargin,lmargin,dmargin,m,n,p,q,t,x,sx,sy,patx[1000001],paty[1000001],map[1001][1001],num,pnum;
bool flag;
int main() {
scanf("%d",&t);
for (int i=0;i<t;++i){
flag=true;
num=0;
lmargin=0;
rmargin=0;
dmargin=0;
pnum=0;
scanf("%d%d%d%d",&m,&n,&p,&q);
for (int j=0;j<m;++j)
for (int k=0;k<n;++k) {
scanf("%d", &map[j][k]);
if (map[j][k]) pnum++;
}
for (int j=0;j<p;++j)
for (int k=0;k<q;++k)
{
scanf("%d",&x);
if (x){
if (num==0) {
sx=j;
sy=k;
num++;
}
else{
patx[num]=j-sx;
paty[num]=k-sy;
if (paty[num]<0)
lmargin=max(lmargin,paty[num]);
rmargin=max(rmargin,paty[num]);
dmargin=max(dmargin,patx[num]);
num++;
}
}
}
for (int j=0;j<m-dmargin;++j){
for (int k=lmargin;k<n-rmargin;++k)
if (map[j][k]){
map[j][k]=0;
for (int l=1;l<num;++l)
if (!map[j+patx[l]][k+paty[l]]) {
flag = false;
break;
}
else
map[j+patx[l]][k+paty[l]]=0;
if (!flag) break;
pnum-=num;
if (!pnum) break;
}
if (!flag) break;
if (!pnum) break;
}
if (!flag) printf("No\n");
else printf("Yes\n");
}
return 0;
}
``````

## yyong119's solution

``````#include <iostream>
#include <queue>

using namespace std;
priority_queue <int, vector<int>, greater<int> > que;
long n, cost, temp;

int main() {

cin>>n;
for (int i = 0; i < n; i++) {
cin>>temp;
que.push(temp);
}

while (que.size() != 1) {
temp = que.top(); que.pop();
temp += que.top(); que.pop();
cost +=temp; que.push(temp);
}
cout<<cost;
}
``````