/ Vijos / 题库 / 合并果子 /

题解

535 条题解

  • 0
    @ 2021-02-24 18:53:44

    //STL大法好
    #include<bits/stdc++.h>
    using namespace std;
    int n,x,ans;
    priority_queue<int,vector<int>,greater<int> >q;
    int main()
    {
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    cin>>x,q.push(x);
    }
    while(q.size()>=2)
    {
    int a=q.top(); q.pop();
    int b=q.top(); q.pop();
    ans+=a+b;
    q.push(a+b);
    }
    cout<<ans<<endl;
    return 0;
    }

  • 0
    @ 2020-11-28 20:34:53

    蒟蒻一开始循环每次都排序50分

    然后蒟蒻在标签的提示下想到了优先队列

    C++党有个福利：

    我们有** STL ** ！！！

    STL里的优先队列 : priority_queue

    #include<bits/stdc++.h>
using namespace std;
int n,x,ans;
priority_queue<int,vector<int>,greater<int> >q;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>x,q.push(x);
    while(q.size()>=2){
        int a=q.top(); q.pop();
        int b=q.top(); q.pop();
        ans+=a+b;
        q.push(a+b);
    }
    cout<<ans<<endl;
    return 0;
}

    其实用堆也行，但是懒得打了
    期待你们理解后AC！

  • 0
    @ 2020-01-16 20:03:55

    用python内置的堆排序模块

    import sys
is_py2 = (sys.version_info[0] == 2) #is_py3 = (sys.version_info[0] == 3)
import heapq

N = input()
if is_py2: vals = map(int, raw_input().split()) # python2 用 raw_input()
else: vals = list(map(int, input().split())) # python3加list转换map返回的迭代器

def work_sum(vals):
    # 此行避免输入为[5]之类单元素列表时出错,sum可保证[]被正确处理
    if(len(vals)<=1): return sum(vals)
        
    ans = 0
    heapq.heapify(vals)
    while len(vals) > 1:
        cur_cost = sum([heapq.heappop(vals) for i in range(2)])
        ans += cur_cost
        heapq.heappush(vals, cur_cost)
    return ans

print(work_sum(vals))
  • 0
    @ 2019-12-28 04:30:07

    我也觉得STL大法好，这种题自己实现数据结构或者每次循环都自己实现排序，真的就是不会priority_queue或者觉得自己刷题的时间太多了可以浪费在上面。
    Keep It Simple and Stupid

    #include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main(int argc, char *argv[]) {
#ifdef DEBUG
    freopen("a.in", "r", stdin);
#endif
    int n, x;
    priority_queue<int, vector<int>, greater<int> > p;

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

    int sum = 0, a, b;
    for (int i = 0; i < n - 1; ++i) {
        a = p.top(); p.pop();
        b = p.top(); p.pop();
        sum += a + b;
        p.push(a + b);
    }
    cout << sum << endl;
    return 0;
}
  • 0
    @ 2019-08-02 17:00:16

    使用列表及其排序会严重超时
    使用 堆heapq模块 来解决即可

    import heapq

n = int(input())
weight_str = input().split()
weight_int = []
for w in weight_str:
    weight_int.append(int(w))
heapq.heapify(weight_int)

cost = 0
for i in range(0,n-1):
    min_1 = heapq.heappop(weight_int)
    min_2 = heapq.heappop(weight_int)
    sum_temp = min_1 + min_2
    heapq.heappush(weight_int, sum_temp)
    cost += sum_temp

print(cost)
  • 0
    @ 2019-07-29 23:38:20

    用最小堆才是正解^-^：
    #include<iostream>
    #include<algorithm>
    #include <queue>
    #include <vector>
    using namespace std;

    int main(){
    int n,tmp;
    cin>>n;
    priority_queue<int, vector<int>, greater<int> > b;//最小堆
    for(int i=0;i<n;i++){
    cin>>tmp;
    b.push(tmp);
    }

    int sum = 0;
    for(int i=0;i<n-1;i++){
    tmp = b.top();
    b.pop();
    tmp += b.top();
    b.pop();
    b.push(tmp);
    sum+=tmp;
    }

    cout<<sum<<endl;
    return 0;
    }

  • 0
    @ 2019-06-18 07:46:09

    #include <iostream>
    using namespace std;
    int main(void)
    {
    int n;
    long int a[20000]={0};
    long int hp=0,i=0;
    int min_1=0,min_2=1;
    cin>>n;
    for(i=0;i<n;++i)cin>>a[i];
    for(i=0;i<n-1;++i){
    for(int q=0;q<n;++q){
    if(a[min_1]>a[q]){
    min_1=q;
    }
    }
    for(int q=0;q<n;++q){
    if(a[min_2]>a[q]&&min_1!=q){
    min_2=q;
    }
    }
    hp+=a[min_1]+a[min_2];
    a[min_1]+=a[min_2];
    a[min_2]=2147483647;
    }
    cout<<hp;
    return 0;
    }

  • 0
    @ 2019-05-05 20:12:00

    #include<iostream>
    #include<queue>
    #include<algorithm>
    using namespace std;
    int n,a[10005],ans;
    priority_queue<int,vector<int>,greater<int> >q;
    int main()
    {
    cin>>n;
    for(int i=0;i<n;i++)
    {
    cin>>a[i];
    q.push(a[i]);
    }
    while(!q.empty())
    {
    int s1=0,s2=0;
    s1=q.top();
    q.pop();
    if(q.empty()) break;
    s2=q.top();
    q.pop();
    ans=s1+s2+ans;
    q.push(s1+s2);
    }
    cout<<ans;
    return 0;
    }/*优先队列：
    头文件：#include<queue>
    具体写法：
    由小到大：priority_queue<int,vector<int>,greater<int> >q;
    由大到小：priority_queue<int,vector<int>,less<int> >q;
    队首元素用q.top()表示*/

  • 0
    @ 2018-12-25 22:06:33

    STL大法好!

    #include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
//呵呵
//大神万岁
//分割线--------------------------------------------------$
//结构定义区
//全局变量区
priority_queue<int,vector<int>,greater<int> > piles;
int n,a;
long long ans=0;
//函数声明区

//主函数开始！
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a;
        piles.push(a);
    }
    while(piles.size()!=1)
    {
        int b,c;
        b=piles.top();
        piles.pop();
        c=piles.top();
        piles.pop();
        piles.push(b+c);
        ans+=(b+c);
    }
    cout<<ans;
    return 0;
}
//函数实现区
  • 0
    @ 2018-11-08 11:03:50

    #include<bits/stdc++.h>
    using namespace std;
    int main()
    {
    int n,i,j,k,sum=0;
    cin>>n;
    int a[n];
    for(i=0;i<n;i++)
    cin>>a[i];
    sort(a,a+n);
    for(i=1;i<n;i++)
    {
    if(i!=1&&i!=n-1)
    for(j=i-1;j<n-1;j++)
    {
    if(a[j]>a[j+1])
    k=a[j],a[j]=a[j+1],a[j+1]=k;
    else

    break;
    }
    a[i]+=a[i-1];
    sum+=a[i];
    }
    cout<<sum;
    return 0;
    }

  • 0
    @ 2018-11-08 11:01:32

    最简单的方法
    #include<bits/stdc++.h>
    using namespace std;
    int main()
    {
    int n,i,j,k,sum=0;
    cin>>n;
    int a[n];
    for(i=0;i<n;i++)
    cin>>a[i];
    sort(a,a+n);
    for(i=1;i<n;i++)
    {
    if(i!=1&&i!=n-1)
    for(j=i-1;j<n-1;j++)
    if(a[j]>a[j+1])
    k=a[j],a[j]=a[j+1],a[j+1]=k;
    else

    break;
    a[i]+=a[i-1];
    sum+=a[i];
    }
    cout<<sum;
    return 0;
    }

  • 0
    @ 2018-10-18 14:06:51

    #include <iostream>
    using namespace std;

    int* a;
    int n;

    int sort(){
    int min;
    for(int i=0;i<n;i++){
    min=i;
    for(int j=i+1;j<n;j++){
    if(a[j]<a[min])
    min=j;
    }
    int l=a[i];
    a[i]=a[min];
    a[min]=l;
    }

    }
    int main()
    {

    cin >> n;
    a=new int[n];

    for(int i=0;i<n;i++){
    cin >> a[i];
    }
    sort();
    int g=a[0];
    int l=0;
    for(int i=1;i<n;i++){
    //cout << a[i]<<endl;
    l += g+a[i];
    g=l;
    }
    cout << l <<endl;
    }

  • 0
    @ 2018-10-01 22:01:54

    刚开始无脑排序，虽然过了但是太慢，换优先队列就很快了

    #include <iostream>
#include <cstdlib>
#include <queue>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cin>>n;
    /*
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    int ans=0;
    for(int i=1;i<n;i++)
    {
        ans+=a[i]+a[i-1];
        a[i]+=a[i-1];
        sort(a+i,a+n);
    }
    */
    priority_queue< int,vector<int>,greater<int> > q;
    int t;
    for(int i=0;i<n;i++)
    {
        cin>>t;
        q.push(t);
    }
    int ans=0;
    while(q.size()>1)
    {
        t=0;
        t+=q.top();
        q.pop();
        t+=q.top();
        q.pop();
        q.push(t);
        ans+=t;
    }
    cout<<ans<<endl;
    return 0;
}
  • 0
    @ 2018-09-11 20:38:58

    #include<iostream>
    #include<algorithm>
    using namespace std;
    int a[10001] = { 0 };
    int book[10001] = { 0 };
    int main()
    {
    int n,sum=0; //果子的种类数 消耗的体力
    cin >> n;
    int temp = n;
    for (int i = 0; i < n; i++)
    cin >> a[i];
    int a_index= 0,book_index=0;
    sort(a, a + n);
    while (temp != 1)
    {
    book[book_index] = a[a_index] + a[a_index + 1];
    a[a_index + 1] += a[a_index];
    temp--;
    a_index++;
    sort(a + a_index, a + n);
    book_index++;

    }
    for (int i = 0; i <= book_index; i++)
    sum += book[i];
    cout << sum;
    return 0;
    }

  • 0
    @ 2018-09-05 15:25:36

    洛谷大佬题解
    观望中...
    正文！！！

      #include<bits/stdc++.h>//（万能库）
    using namespace std;
    int a[100000];//(用一个数组来代替队列)
    int main(){
    int n,sum=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];//（读入数据）
    }
    sort(a+1,a+n+1);//（初始排序）
    while(1){//（开始合并循环，其实可以用for代替）
        int j=1;
        while(a[j]==0)
        j++;
        //（其实这里懒了，当时做的时候用的是sort,可以用别的做法）
        if(j==n) break;//（此时只存在一个堆，退出循环）
        else {
            a[j]+=a[j+1];
            sum+=a[j];//（i和j 合并成一个果堆，增加所用的力气）
            for(int l=j+1;l<n;l++)
             {
                a[l]=a[l+1];//（将j后面的果堆向前一位）
            }
            n--;//（减少一个堆）
        }
        for(int l=j;l<n;l++)
        {
            if(a[l]>a[l+1])//（为新的堆找到位置）
            {
                swap(a[l],a[l+1]);
            }
        }
    }
    cout<<sum;//（输出力气）
    return 0;//（功德圆满）
    }
**加油吧，神犇们！！！**
*如有需要改进的地方，还请各位大佬提出建议（引用大佬的话语，不是本人(ˉ(∞)ˉ)）*
> 欢迎指出bug
> 不喜勿喷，thanks
  • 0
    @ 2018-08-01 15:18:54

    #include <bits/stdc++.h>
    using namespace std;
    int main()
    {
    priority_queue<int, vector<int>, greater<int>> minHeap;
    int result=0,n,tmp;
    cin>>n;
    for(int i=0;i<n;i++)
    {
    cin>>tmp;
    minHeap.push(tmp);
    }
    while(1)
    {
    tmp=minHeap.top();
    minHeap.pop();
    tmp+=minHeap.top();
    minHeap.pop();
    result+=tmp;
    if(minHeap.empty()) break;
    minHeap.push(tmp);
    }
    cout<<result<<endl;
    }

  • 0
    @ 2018-07-29 22:30:29

    #include<bits/stdc++.h>
    using namespace std;
    priority_queue<int,vector<int>,greater<int> >q;
    int main()
    {
    int k,n,a,b,sum=0;
    cin>>n;
    for (int i=1;i<=n;i++)
    {
    cin>>k;
    q.push(k);
    }
    while (q.size()>1)
    {a=q.top();
    q.pop();
    b=q.top();
    q.pop();
    q.push(a+b);
    sum+=a+b;
    }

    cout<<sum<<endl;
    return 0;
    }

  • 0
    @ 2018-07-28 09:39:01

    #include<iostream>

    using namespace std;

    int main()
    {
    int n,tot(0);
    cin>>n;
    int a[n+1];
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=1;i<=n;++i)//先整体排序
    for(int j=i+1;j<=n;++j)
    if(a[j]<a[i])swap(a[j],a[i]);

    for(int i=1;i<=n-1;++i)//n-1次合并
    {
    a[i+1]=a[i]+a[i+1];//不管a[i]了相当于删去a[i]
    tot+=a[i+1];//累加耗费体力=每次把前两堆合起来用的体力体力
    for(int j=i+1;j<=n-1;++j)
    if(a[j]>a[j+1])swap(a[j],a[j+1]);//将a[i+1]换到合适的位置
    }
    cout<<tot;
    return 0;
    }

  • 0
    @ 2018-07-24 20:13:28

    优先队列而已，http://www.cppblog.com/shyli/archive/2007/04/06/21366.html
    #include<bits/stdc++.h>
    using namespace std;
    priority_queue<int,vector<int>,greater<int> >s;//建一个以小为优先级的优先队列
    int main()
    {
    int o,p,maxx,n,i,k;
    cin>>n;
    for(i=1;i<=n;i++)
    {
    cin>>k;
    s.push(k);//入列
    }
    for(i=1;i<=n-1;i++)//n-1次后，合并结束
    {
    o=s.top();
    s.pop();
    p=s.top();
    s.pop();
    maxx+=o+p;
    s.push(o+p);
    }
    cout<<maxx;
    return 0;
    }

  • 0
    @ 2018-06-28 09:14:03

    #include <iostream>
    #include <algorithm>

    using namespace std;

    void MinSum(int n,int arr[20001]);

    int main()
    {
    int n;
    int arr[20001]={0};
    cin >> n;
    for(int i=0;i<n;i++) {
    cin >> arr[i];
    }
    sort(arr,arr+n); //降序排序
    MinSum(n,arr); //计算最小和
    return 0;
    }

    void MinSum(int n,int arr[200000]) {
    int sum=0;
    for(int i=0;i<n;i++) {
    if(i<n-1) //遍历数组，第一个和最后一个元素不影响整体结果
    {
    arr[i+1]=arr[i]+arr[i+1]; //计算局部和
    sum+=arr[i+1];

    sort(arr+i,arr+n); //重排序
    }
    }
    cout << sum << endl;
    }

合并果子

信息

ID
1097
难度
6
分类
贪心 点击显示
标签
递交数
23906
已通过
6330
通过率
26%
被复制
41
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1