首页 > 试题广场 >

搬水果

[编程题]搬水果
  • 热度指数：10328 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
    在一个果园里，小明已经将所有的水果打了下来，并按水果的不同种类分成了若干堆，小明决定把所有的水果合成一堆。每一次合并，小明可以把两堆水果合并到一起，消耗的体力等于两堆水果的重量之和。当然经过 n‐1 次合并之后，就变成一堆了。小明在合并水果时总共消耗的体力等于每次合并所耗体力之和。     假定每个水果重量都为 1，并且已知水果的种类数和每种水果的数目，你的任务是设计出合并的次序方案，使小明耗费的体力最少，并输出这个最小的体力耗费值。例如有 3 种水果，数目依次为 1，2，9。可以先将 1，2 堆合并，新堆数目为3，耗费体力为 3。然后将新堆与原先的第三堆合并得到新的堆，耗费体力为 12。所以小明总共耗费体力=3+12=15，可以证明 15 为最小的体力耗费值。

输入描述:
    每组数据输入包括两行,第一行是一个整数 n(1<=n<=10000),表示水果的种类数。第二行包含 n 个整数，用空格分隔，第 i 个整数(1<=ai<=1000)是第 i 种水果的数目。


输出描述:
对于每组输入，输出一个整数并换行，这个值也就是最小的体力耗费值。输入数据保证这个值小于 2^31。
示例1

输入

3
9 1 2
0

输出

15
算法知识视频讲解
添加回答
huangju头像 huangju
这题实质上就是哈夫曼树 
#include <stdio.h>
#include <queue>
using namespace std;
priority_queue<int,vector<int>,greater<int>> Q; //升序优先队列实现最小堆
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
        if(n==0)break;
        while(!Q.empty())Q.pop();
        for(int i=0;i<n;++i)
        {
            int x;
            scanf("%d",&x);
            Q.push(x);
        }
        int ans=0;
        while(Q.size()>1){
            int a=Q.top();
            Q.pop();
            int b=Q.top();
            Q.pop();
            ans+=a+b;
            Q.push(a+b);
        }
        printf("%d\n",ans);
    }
    return 0;
}

发表于 2018-01-14 22:02:03 回复(0)
C/C++
forevergorilla头像 forevergorilla
#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    int number[10000];
    while (scanf_s("%d",&n)!=EOF)
    {
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            scanf_s("%d", &number[i]);
        }
        sort(number, number + n);
        for (int i = 0; i < n-1; i++)
        {
            number[i+1]= number[i] + number[i + 1];
            ans +=number[i + 1];
            sort(number, number + n);
        }
        printf("%d", ans);
    }
    return 0;
发表于 2018-03-15 16:59:59 回复(1)
IOK6头像 IOK6 
#include <iostream>
#include <queue>

using namespace std;

priority_queue<int, vector<int>, greater<int>> Q; //建立小顶堆
int main()
{
    int n; //结点个数
    int x;
    while (cin >> n)
    {
        while (Q.empty() == false)
            Q.pop();
        for (int i = 0; i < n; ++i)
        {
            cin >> x; //输入权值
            Q.push(x);
        }
        int ans = 0, a, b;
        while (Q.size() >= 2)
        {
            a = Q.top(); //去小顶堆中最小的两个元素，他们为某一节点的左右儿子，他俩权值之和为双亲结点的值
            Q.pop();
            b = Q.top();
            Q.pop();
            ans += a + b;
            Q.push(a + b); //将双亲结点push进堆
        }
        cout << ans;
    }
}
发表于 2018-04-24 20:54:06 回复(3)
百变大樱头像 百变大樱 
#include <iostream>

#include <map>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> vc;
    int waste = 0;
    while (n--) {
        int tmp;
        cin >> tmp;
        vc.push_back(tmp);
    }
    if (vc.size() == 1) {
        waste = vc[0];
    } else {
        while (vc.size() > 1) {
            sort(vc.begin(), vc.end());
            int new_heap = vc[0] + vc[1];
            waste += new_heap;
            vc.erase(vc.begin());
            vc.erase(vc.begin());
            vc.push_back(new_heap);
        }
    }
    cout << waste << endl;

    return 0;
}

发表于 2021-01-13 17:47:00 回复(0)
C/C++
妖骨头像 妖骨 
#include<iostream>
#include<string>
#include<stack>
#include<queue>
using namespace std;

priority_queue<int, vector<int>, greater<int> > Q;   //小顶堆

int main()
{
    int n;
    while(scanf("%d", &n) != EOF && n != 0){
        while(!Q.empty()) Q.pop();  //清除之前的数据

        for(int i = 0; i < n; i++){
            int x;
            scanf("%d", &x);
            Q.push(x);
        }

        int ans = 0;
        while(Q.size() > 1){
            int a = Q.top();
            Q.pop();
            int b = Q.top();
            Q.pop();
            ans += a+b; //累加结果
            Q.push(a+b);
        }
        printf("%d\n", ans);
    }
    return 0;
}
编辑于 2020-07-04 23:55:39 回复(0)
C/C++
☆☆浮生若梦头像 ☆☆浮生若梦
哈夫曼树思想！！！ 
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF&&n!=0)
    {
        priority_queue<int,vector<int>,greater<int> >q;
        while(n--)
        {
            int x;
            scanf("%d",&x);
            q.push(x);
        }
        int a=0;
        while(q.size()>1)
        {
            int x=q.top();
            q.pop();
            int y=q.top();
            q.pop();
            a+=x+y;
            q.push(x+y);
        }
        printf("%d\n",a);
    }
    return 0;
}

发表于 2020-04-08 10:06:18 回复(0)
C/C++
YhX.头像 YhX. 

	

c 本质哈夫曼思想,别忘记之前耗费的体力




#include<stdio.h>//哈夫曼树思想
int a[10000],n;
int min()
{
    int i,t=0,m=a[0];//先默认最小的是第一个值
    for(i=1;i<n;i++)
        if(m>a[i])
        {
            m=a[i];//找到最小值
            t=i;//记录最小值的位置
        }
    a[t]=a[n-1];//把最小值的位置存放最后一个值
    n--;//减去一个结点
    return m;
}
int main()
{
    int i,ans=0,min1,min2;
    scanf("%d",&n);
    for(i=0;i<n;i++)//一共n个结点,下标0-n-1
        scanf("%d",&a[i]);
    while(n>1)//因为要找2个min,所以n最小值2
    {
        min1=min();min2=min();//找两个最小值n-2
        ans+=min1+min2;//累加的过程,之前消耗的体力别忘记加所以+=
        a[n]=min1+min2;//新获得的结点
        n++;//新增一个节点
    }
    printf("%d",ans);
}

编辑于 2020-03-27 17:57:54 回复(0)
C/C++
肆年头像 肆年
这题和北邮哈夫曼树那题思路一模一样，只不过这题n最大能取到10000，这时候用小顶堆来取最小值的优势就比较明显了 
#include <stdio.h>
int a[10001];
int next(int i) {
    int min=2*i;
    if(2*i+1<=a[0] && a[2*i+1]<a[2*i])
        min=2*i+1;
    if(a[min]<a[i]) {
        int t=a[i];
        a[i]=a[min];
        a[min]=t;
        return min;
    }
    return a[0]/2+1;
}
void down(int i) {
    while(i<=a[0]/2)
        i=next(i);
}
//小顶堆的初始化
void init() {
    for(int i=a[0]/2; i>=1; i--)
        down(i);
}
//取出数组中最小的两个数，相加得s,将s加入数组，返回s
int sum() {
    int s=a[1];
    a[1]=a[a[0]];
    a[0]--;
    down(1);
    s+=a[1];
    a[1]=s;
    down(1);
    return s;
}
int main() {
    while(scanf("%d",&a[0])!=EOF && a[0]!=0) {
        for(int i=1; i<=a[0]; i++)
            scanf("%d",&a[i]);
        init();
        int ans=0;
        while(a[0]>1)
            ans+=sum();
        printf("%d\n",ans);
    }
    return 0;
}

发表于 2020-03-18 00:29:20 回复(2)
底层搬砖工头像 底层搬砖工 
//数组模拟哈夫曼树合并过程即可，注意快排一次之后后面的数据插入排序，否则会超时
#include <stdio.h>
(737)#include <string.h>
#include <stdlib.h>
int a[10005];
int cmp(const void *a,const void *b){
    return *(int*)a-*(int*)b;
}
int main(){
    int n;
    int i,j;
    int sum;
    int cost;
    while(scanf("%d",&n)!=EOF&&n){
        memset(a,0,sizeof(a));
        for(i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        qsort(a,n,sizeof(int),cmp);
        cost=0;
        for(i=1;i<n;i++){
            sum=a[i-1]+a[i];
            cost+=sum;
            for(j=i+1;j<n;j++){
                if(a[j]>sum) break;
                else a[j-1]=a[j];
            }
            a[j-1]=sum;
        }
        printf("%d\n",cost);
    }
    return 0;
}

发表于 2020-03-15 16:43:59 回复(0)
xxx2023头像 xxx2023 
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n;
	vector<int> fruit;
	int HP=0;
	int temp;
	while(cin>>n){
		if(n==0) return 0;
		for(int i=0;i<n;i++){
			cin>>temp;
			fruit.push_back(temp);
		}
		for(int i=0;i<n-1;i++){
			sort(fruit.begin(),fruit.end());
			HP=HP+(fruit[0]+fruit[1]);
			fruit.push_back(fruit[0]+fruit[1]);
			fruit.erase(fruit.begin(),fruit.begin()+2);
		}
		cout<<HP<<endl;
		fruit.clear();
	}
	return 0;
}

发表于 2020-03-07 14:24:02 回复(0)
Benson666头像 Benson666 
import java.util.Scanner;
import java.util.PriorityQueue;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n = in.nextInt();
            PriorityQueue<Integer> q = new PriorityQueue<Integer>();
            for(int i=0;i<n;i++)
                q.add(in.nextInt());
            int sum = 0;
            while(q.size()>1){
                int a = q.poll();
                int b = q.poll();
                q.add(a+b);
                sum += (a+b);
            }
            System.out.println(sum);
        }
    }
}

发表于 2018-03-05 14:14:11 回复(0)
VagrantYang头像 VagrantYang

插入排序也是可以，只要思想正确，清晰

package com.speical.first;

import java.util.Scanner;

/** 
* 搬苹果
* 
* 代价最小与霍夫曼树的思想是一致的
* 就是每次从苹果堆里选择最小的两堆，然后合并组成新堆，加入到原苹果堆
* 再挑选2个最小堆，直至最后一个堆为止
* 
* 最好的解法当属：优先队列！！
* 当然也可以次优解，此处我给的是插入排序
* 首先进行一次插入排序，然后取首端2个堆，
* 更新第二堆的大小，然后向数组末端方向进行一次插入
* 数组索引加1，相当于我们合并了一个堆，要删除前一个堆
* 重复以上步骤，直到走到数组末端
* @author special
* @date 2018年2月2日 上午11:11:45
*/
public class Pro176 {

    public static void insertSort(int begin, int[] fruits){
        for(int i = begin; i < fruits.length - 1 && fruits[i] > fruits[i + 1]; i++){
            int temp = fruits[i];
            fruits[i] = fruits[i + 1];
            fruits[i + 1] = temp;
        }
    }

    public static void insertSort(int[] fruits){
        for(int i = fruits.length - 2; i >= 0; i--){
            insertSort(i, fruits);
        }
    }

    public static int getMinPrice(int[] fruits){
        insertSort(fruits);
        int price = 0;
        for(int i = 1; i < fruits.length; i++){
            price += fruits[i] + fruits[i - 1];
            fruits[i] += fruits[i - 1];
            insertSort(i, fruits);
        }
        return price;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner input = new Scanner(System.in);
        while(input.hasNext()){
            int n = input.nextInt();
            int[] fruits = new int[n];
            for(int i = 0; i < n; i++){
                fruits[i] = input.nextInt();
            }
            System.out.println(getMinPrice(fruits));
        }
    }

}
发表于 2018-02-02 11:38:05 回复(0)
fine___头像 fine___ 
#include<iostream>
#include<queue>
#include<functional>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
 int n;
 while (cin >> n&&n) {
  priority_queue<int, vector<int>, greater<int>> q;
  for (int i = 0; i < n; ++i) {
   int tmp;
   cin >> tmp;
   q.push(tmp);
  }
  int res = 0;
  while (q.size()>1) {
   int a = q.top(); q.pop();
   int b = q.top(); q.pop();
   q.push(a + b);
   res += a + b;
  }
  cout << res << endl;
 }
 return 0;
}

发表于 2017-09-01 16:12:49 回复(0)
EresonSum头像 EresonSum
解法一： 
使用STL的队列 
#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int, vector<int>, greater<int> > pending;
    int N, x, temp_1, temp_2, result;
    while (cin >> N && N) {
        result = 0;
        while (!pending.empty())
            pending.pop();
        while (N--) {
            cin >> x;
            pending.push(x);
        }
        while (pending.size() > 1) {
            temp_1 = pending.top();
            pending.pop();
            temp_2 = pending.top();
            pending.pop();
            result += temp_1 + temp_2;
            pending.push(temp_1 + temp_2);
        }
        cout << result << endl;
    }
    return 0;
}
方法二：
先排序后累加 
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    int N;
    while (cin >> N) {
        int FruitsKind[N], zero;
        for (int i = 0; i < N; i++)
            cin >> FruitsKind[i];
        cin >> zero;
        sort(FruitsKind, FruitsKind + N);
        int temp = FruitsKind[0], Engergy = 0;
        for (int i = 1; i < N; i++) {
            temp += FruitsKind[i];
            Engergy += temp;
        }
        cout << Engergy << endl;
    }
    return 0;
}

发表于 2017-02-15 12:02:07 回复(3)
C++
帅奶哟。头像 帅奶哟。 
#include <cstdio>
#include <iostream>
#include <queue>

using namespace std;

// 本质就是 计算哈夫曼树的带权路径长度和 
int main() {
	int n;
	while (scanf("%d", &n) != EOF) {
		if (n == 0) {
			break;
		}
		
		// 优先队列 
		priority_queue<int> pqueue;
		for (int i = 0; i < n; i++) {
			int x;
			scanf("%d", &x);
			pqueue.push(-x);// 注意是负号，因为要模拟小根堆 
		}
		
		int res = 0;// 保存加权路径长度 
		while (pqueue.size() > 1) {
			// 弹出两个最小的 
			int leaf1 = pqueue.top();
			pqueue.pop();
			int leaf2 = pqueue.top();
			pqueue.pop();
			res = res + leaf1 + leaf2;// 加权路径长度 
			pqueue.push(leaf1 + leaf2);// 压入队列 
		}
		// 当只剩一个时，即为最小体力耗费值 
		printf("%d\n", -res);// 注意负号 
	}
	return 0; 
}

发表于 2023-03-26 20:54:41 回复(0)
复旦周杰伦头像 复旦周杰伦 
/// 注意   :  此动态 规划 是 只能合并相邻的两堆
/// 哈夫曼树  是 每次合并可以 从堆中 任意挑选 两堆


// ///状态表示: 集合: 第i堆到第j堆 合并的所有情况   属性: 代价最小
// /// 状态计算 : f[i][j] = min(f[i][k]+f[k][j]) + s[j]-s[i-1]

// //// 为什么动态规划 AC不了啊
// // 我这个 动规 有问题吗
// #include "iostream"
// #include "cstdio"
// #include "algorithm"
// using namespace std;
// const int N = 10010;
// int n;
// int f[N][N];
// int s[N];
// int main() {
//     cin >> n;
//     for (int i = 1; i <= n; i++) {
//         scanf("%d", &s[i]);
//         s[i] += s[i - 1];
//     }
//     for (int len = 2; len <= n; len++) {
//         for (int i = 1; i + len - 1 <= n; i++) {
//             int l = i, r = i + len - 1;
//             f[l][r] = 1e9;
//             for (int k = l; k < r; k++) {
//                 f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
//             }

//         }

//     }
//     cout << f[1][n] << endl;

// }
#include <functional>
#include<iostream>
#include "algorithm"
#include <cstring>
#include <vector>
#include "queue"
using namespace std;

int n;
int answer;
int main() {
    priority_queue <int , vector<int>,greater<int>> q;
    cin >> n;
    while (n -- ) {
       int x;
       cin >>x;
       q.push(x);
    }
    while(q.size()>1){
        int a=q.top();
        q.pop();
        int b=q.top();
        q.pop();
        answer += a+b;
        q.push(a+b);
    }
    cout << answer <<endl;





    return 0;
}

发表于 2023-03-18 10:38:25 回复(0)
C/C++
猫猫猫1头像 猫猫猫1
#include<bits/stdc++.h>
using namespace std;

int main() {
    int n;
    while(cin>>n) {
        priority_queue<int,vector<int>,greater<int> > q;
        while(n--) {
            int x;
            cin>>x;
            q.push(x);
        }
        int answer=0;
        while(q.size()>1) {
            int a=q.top();
            q.pop();
            int b=q.top();
            q.pop();
            answer+=a+b;
            q.push(a+b);
        }
        cout<<answer<<endl;
    }
    return 0;
}
发表于 2022-10-12 21:27:06 回复(0)
zbt_123456头像 zbt_123456 
#include <iostream>
#include<queue>
using namespace std;
int main() {
    int n;
    while(cin>>n&&n!=0){
        priority_queue<int,vector<int>,greater<>> q;
        while(n--){
            int x;
            cin>>x;
            q.push(x);
        }
        int ans = 0;
        while(q.size()>1){
            int a = q.top();
            q.pop();
            int b = q.top();
            q.pop();
            ans += a + b;
            q.push(a + b);
        }
        cout<<ans<<endl;
    }
    return 0;
}

发表于 2024-03-30 12:51:25 回复(0)
C++
牛客390280000号头像 牛客390280000号
#include <iostream>
#include <queue>

using namespace std;

int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        if(n==0){break;}
        priority_queue<int,vector<int>,greater<int>> Q;
        for(int i=0;i<n;i++){
            int a;
            cin>>a;
            Q.push(a);
        }
        int x,y;
        int ans=0;
        while(Q.size()>1){
            x=Q.top();
            Q.pop();
            y=Q.top();
            Q.pop();
            ans=ans+x+y;
            Q.push(x+y);
        }
        cout<<ans<<endl;
    }
}
// 64 位输出请用 printf("%lld")
发表于 2024-03-07 14:43:02 回复(0)
C++
ARMOUR072头像 ARMOUR072
还以为是区间合并，，看岔劈了
编辑于 2024-03-05 11:11:01 回复(0)
提交观点

问题信息

贪心
难度：
74条回答 6991浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号