NOIp中很少见的数据结构的题目,可以用堆实现,也可以用两条队列. 用堆实现,调了很久 = =
需要注意down函数的边界问题.
1
#include<stdio.h>
2
#include<string.h>
3
#include<iostream>
4
using namespace std;
5
int n, h[10010];
6![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct heap
{
7![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
void swap(int*i, int*j)
{
8
int k = *i; *i = *j; *j = k;
9
}
10![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
void up(int k)
{
11
while (k > 1)
12![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (h[k/2] > h[k])
{
13
swap(&h[k/2], &h[k]);
14
k /= 2;
15
}else break;
16
}
17![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
void down(int k)
{
18![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while (2*k <= n)
{
19
int l = 2*k, r = l<n ? l+1 : l;
20
if (h[r] < h[l]) l++;
21![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (h[k] > h[l])
{
22
swap(&h[k], &h[l]);
23
k = l;
24
}else break;
25
}
26
}
27![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
void insert(int x)
{
28
h[++n] = x;
29
up(n);
30
}
31![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
void del(int k)
{
32
swap(&h[k], &h[n--]);
33
34
down(k);
35
}
36![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
int pop()
{
37
del(1);
38
return h[n+1];
39
}
40
};
41
heap hp;
42![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
43
int i, sum = 0;
44
scanf("%d", &n);
45
for (i = 1; i <= n; i++)
46
scanf("%d", &h[i]);
47
for (i = n/2; i > 0; i--) hp.down(i);
48![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while (n > 1)
{
49
int x = hp.pop(), y = hp.pop();
50
sum += x+y;
51
hp.insert(x+y);
52
}
53
printf("%d\n", sum);
54
}
55![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)