洛谷P1090$\lfloor$NOIP2004提高组$\rceil$题解

发表于 | 更新于 | 评论数： | 阅读次数：

P1090合并果子

题目描述

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过
$n−1$次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 $1$ ，并且已知果子的种类 数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

输入输出格式

输出格式

共两行。
第一行是一个整数$n$，$(1 \leq n \leq 10^4)$表示果子的种类数。
第二行包含 $n$个整数，用空格分隔，第$i$个整数$a_i(1 \leq a_i \leq 2*10^4)$ 是第 $i$ 种果子的数目。

输出格式

一个整数，也就是最小的体力耗费值。输入数据保证这个值小于$2^{31}$.

INPUT & OUTPUT’s examples

Input’s eg #1

1
2
3 
1 2 9

Output’s eg #1

1
15

分析

粗略的看了以下，貌似各位dalao是贪心+堆优化的居多，应该是就我一个最优二叉树。。。

好，现在开始正经。

把题意简化一下，就是说给定$n$个节点，每个节点有一个权值$v_i$,将他们中的每两个合并为树，假设每个节点从根到他自己的距离是$d_i$,最终的目标就是让$\sum_{i=1}^n v_id_i$最小，于是，问题就变成了最优二叉树，

这里介绍使用两个线性表的做法：

定义两个线性表A[]和B[],其中A[]表示存放原来n堆果子数，并按从小到大的顺序排列，B[]存放新合并的果子数。
因为合并后的果子数一定不会少于合并前的果子数(废话吗QAQ)，新加入的数一定插入在B[]的尾部。

所以，每一次合并就要分两步：
1.在A[]和B[]的头部取数，又分为AA、AB、BB三种。
2.合并后的新数加入B[]的尾部。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/* Headers */
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cctype>
#include<cstring>
/* consts */
const int MAXN = 30010;
using namespace std;
namespace FastIO{
    const int BUFSIZE=(1<<20);
    char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==it)
            it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==it)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }
        return neg?-res:res;
    }
    inline void write(int x){
    	if(x<0) putchar('-'),x=-x;
    	if(x>9) write(x/10);
    	putchar(x%10+'0');
    }
    inline void space(int x){
        if(x!=0) putchar(' ');
        else putchar('\n');
    }
} 
using namespace FastIO;
/* defintions */
int A[MAXN],B[MAXN];
int n,ans,x,y;
int p,q,m;
inline void init(){
	scanf("%d",&n);
	for(int i=0;i<=n-1;i++){
		scanf("%d",&A[i]);
	} 
}
inline int find_min(){
	int minx=1e8,mini=0;
	if(p<n&&A[p]<minx){minx=A[p];mini=1;}
	if(q<=m&&B[q]<minx){minx=B[q];mini=2;}
	if(mini==1)p++;
	else q++;
	return minx;
}
inline void work(){
	init();
	sort(A,A+n);
	ans=A[0]+A[1];B[0]=A[0]+A[1]; 
	p=2;q=0;m=0;
	for(int i=1;i<n-1;i++){
		x=find_min();y=find_min();
		B[++m]=x+y;
		ans+=x+y;
	}
	printf("%d\n",ans); 
}
int main(int argc,char *argv[]){
	work();
	return 0;
}

THE END