题解

527 条题解

  • 11
    @ 2017-05-17 16:31:10
    #include<stdio.h>
    int main()
    {
        int n, a[10000];
        scanf("%d", &n);
        int i, min1, min2;
        int sum = 0;
        for (i = 0; i < n; i++)
            scanf("%d", &a[i]);
        min1 = 0, min2 = 1;                   //其实初始化min1和min2是0或者1都无所谓
        int t = n - 1;                        //注意到这里要复制一个n
        while (t--)                           //是先判断t,再自减,故上一行需要n-1
        {
            for (i = 0; i < n; i++)           //找到最小值和次小值的下标,无论min1和min2值如何,都可以找到最小和次小
            {
                if (a[i] < a[min1])
                {
                    min2 = min1;
                    min1 = i;
                }
                else if (a[i] >= a[min1] && a[i] < a[min2] && i != min1)
                    min2 = i;
            }
            sum += a[min1] + a[min2];
            a[min2] += a[min1];           //把次小值更新为和
            a[min1] = 99999999;           //把最小值标记为一个足够大的值
        }
        printf("%d", sum);
        return 0;
    }
    
    
  • 2
    @ 2021-04-18 11:59:35

    首先看到各位大佬用的都是堆或桶我也就放心了
    当然我做这道题的思路也是堆

    但是,简单的介绍堆并不是我写这道题的目的

    我写这篇题解,是为了让各位了解一下大家平时很少注意的C++的某个方面
    发掘更多新玩法

    把你们从算法的深渊拉出来

    —————————————分割线———————————————

    ————————————正文开始———————————————

    ————————————此篇为C++福利——————————

    第一部分
    设想一下,某一天,当你兴致勃勃的在vijos里刷题时,看到了一道叫“合并果子”的题,你不屑地扫了一遍题目,心想着这种模板题也好意思入选提高组。迅速用小根堆将它AC后,却对堆产生了浓厚兴趣,便又找来一道与堆有关的题,惊讶发现该题的数据long long装不下,于是又写了一篇高精,但是在结合两者时却死活都结合不了,最后关掉电脑,生无可恋。

    换一个场景,很多人都用过,至少接触过C++的STL库,那么应该就很熟悉形似这样的东西

    priority_queue < int, vector<int>, greater<int> >;
    vector < long long >;
    queue <double >;
    

    一些细心的人可能就会发现,在<>简直可以装下任何数据类型,那么C++,到底是如何实现这种操作的呢?

    —————————分割线——————————

    —————————分割线——————————

    —————————分割线——————————

    第二部分
    我们回到第一个设想,你在写了一篇堆模板后,为了让它能够支持不同数据类型,对代码进行了这样的改动

    typedef item int;
    class heap{
        private:
            item h[1001];
            int len;
        public:
            heap();
            void push(item const &);
            void pop();
    }
    

    这样就可以针对不同数据类型,运用不同的堆

    typedef item long long;
    class heap{
        private:
            item h[1001];
            int len;
        public:
            heap();
            void push(item const &);
            void pop();
    }
    typedef item string;
    class heap{
        private:
            item h[1001];
            int len;
        public:
            heap();
            void push(item const &);
            void pop();
    }
    

    但这样却有两个致命的缺陷,那就是每次使用,都得改一下头文件,并且不能同时存在两个不同类型的堆。那么应该怎样做呢?你不禁陷入了沉思。

    第三部分
    聪明的你当然知道如何使用网络来使自己的生活更加便利,于是你在“百度一下”中打出了

    priority_queue < int, vector<int>, greater<int> >
    并按下了回车,结果跳出来满屏的“容器”啊,“CSDN博客”啊之类的,让你心烦意燥,分分钟原地爆炸。或是瞅着顺眼的点了一篇,耐着性子看完,最后学到了NOTHING。

    但是,一个词语突然从你眼前闪过,这个词语仿佛有着魔力,使你的视线一下子聚焦在了它身上,你的脑中仿佛浮现出了什么,又仿佛没有。

    “类模板”
    你轻轻地念叨着这词。

    第四部分
    类模板,模板的类型参数由关键字class 或关键字typename 及其后的标识符构成。在模板参数表中关键字class 和typename 的意义相同。(在标准C++之前关键字typename 没有被支持 ,把这个关键字加入到C++中的原因是因为有时必须要靠它来指导编译器解释模板定义。),是对一批仅仅成员数据类型不同的类的抽象,程序员只要为这一批类所组成的整个类家族创建一个类模板,给出一套程序代码,就可以用来生成多种具体的类,(这类可以看作是类模板的实例),从而大大提高编程的效率。————360百科
    我们举个列子:

    template<typename item>
    class smallest_heap{
        private:
            item heap[10001];
            int len;
        public:
            smallest_heap();
            void push(item const &);
            void pop();
            item top();
            int size();
            bool empty();
            
    };
    

    其中第一排的

    template<typename item>
    

    就是关键,它指出接下来声明的某个类是模板,也就是部分数据类型不确定,暂且将这种数据类型叫做

    item
    

    而方法(也就是成员函数),相信各位大佬都会写。但是,要注意,在操作时,有一些不同指出

    template<typename item>
    smallest_heap<item>::smallest_heap(){
        len=0;
        memset(heap,0,sizeof(heap));
    }
    
    template<typename item>
    void smallest_heap<item>::push(item const &n){
        heap[++len]=n;
        int son=len,father=son/2;
        while(heap[son]<heap[father] && father>=1){
            swap(heap[son],heap[father]);
            son=father,father=son/2;
        }
    }
    
    template<typename item>
    void smallest_heap<item>::pop(){
        swap(heap[1],heap[len]);
        heap[len--]=0;
        int father=1,son=2;
        while(son<=len){
            if(son<len && heap[son]>heap[son+1]) son++;
            if(heap[father]>heap[son]){
                swap(heap[father],heap[son]);
                father=son,son=father*2;
            }else break;
        }
    }
    
    template<typename item>
    item smallest_heap<item>::top(){
        return heap[1];
    }
    
    template<typename item>
    int smallest_heap<item>::size(){
        return len;
    }
    
    template<typename item>
    bool smallest_heap<item>::empty(){
        return len;
    }
    

    在每个方法前,都加了一排

    template<typename item>
    这是因为类的数据类型不确定,自然方法数据类型也不确定,所以用

    item
    来替代。并且在声明方法所属域时,也不是

    smallest_heap::smallest_heap()
    而是

    smallest_heap<item>::smallest_heap()
    最后送上AC代码以及小根堆,大根堆模板一份

    > 番外
    AC代码

    #include<iostream>
    #include<cstring>
    using namespace std;
    
    template<typename item>
    class smallest_heap{
        private:
            item heap[10001];
            int len;
        public:
            smallest_heap();
            void push(item const &);
            void pop();
            item top();
            int size();
            bool empty();
            
    };
    
    template<typename item>
    smallest_heap<item>::smallest_heap(){
        len=0;
        memset(heap,0,sizeof(heap));
    }
    
    template<typename item>
    void smallest_heap<item>::push(item const &n){
        heap[++len]=n;
        int son=len,father=son/2;
        while(heap[son]<heap[father] && father>=1){
            swap(heap[son],heap[father]);
            son=father,father=son/2;
        }
    }
    
    template<typename item>
    void smallest_heap<item>::pop(){
        swap(heap[1],heap[len]);
        heap[len--]=0;
        int father=1,son=2;
        while(son<=len){
            if(son<len && heap[son]>heap[son+1]) son++;
            if(heap[father]>heap[son]){
                swap(heap[father],heap[son]);
                father=son,son=father*2;
            }else break;
        }
    }
    
    template<typename item>
    item smallest_heap<item>::top(){
        return heap[1];
    }
    
    template<typename item>
    int smallest_heap<item>::size(){
        return len;
    }
    
    template<typename item>
    bool smallest_heap<item>::empty(){
        return len;
    }
    
    
    smallest_heap<int> h;
    int n,ans;
    int main(){
        cin>>n;
        for(int i=1;i<=n;i++){
            int a;
            cin>>a;
            h.push(a);
        }
        while(h.size()>1){
            int x=h.top(); h.pop();
            int y=h.top(); h.pop();
            h.push(x+y);
            ans+=x+y;
        }
        cout<<ans;
        return 0;
    }
    小根堆
    
    #include<cstring>
    
    template<typename item>
    class smallest_heap{
        private:
            item heap[10001];
            int len;
        public:
            smallest_heap();
            void push(item const &);
            void pop();
            item top();
            int size();
            bool empty();
            
    };
    
    template<typename item>
    smallest_heap<item>::smallest_heap(){
        len=0;
        memset(heap,0,sizeof(heap));
    }
    
    template<typename item>
    void smallest_heap<item>::push(item const &n){
        heap[++len]=n;
        int son=len,father=son/2;
        while(heap[son]<heap[father] && father>=1){
            swap(heap[son],heap[father]);
            son=father,father=son/2;
        }
    }
    
    template<typename item>
    void smallest_heap<item>::pop(){
        swap(heap[1],heap[len]);
        heap[len--]=0;
        int father=1,son=2;
        while(son<=len){
            if(son<len && heap[son]>heap[son+1]) son++;
            if(heap[father]>heap[son]){
                swap(heap[father],heap[son]);
                father=son,son=father*2;
            }else break;
        }
    }
    
    template<typename item>
    item smallest_heap<item>::top(){
        return heap[1];
    }
    
    template<typename item>
    int smallest_heap<item>::size(){
        return len;
    }
    
    template<typename item>
    bool smallest_heap<item>::empty(){
        return len;
    }
    大根堆
    
    #include<cstring>
    
    template<typename item>
    class largest_heap{
        private:
            item heap[10001];
            int len;
        public:
            largest_heap();
            void push(item const &);
            void pop();
            item top();
            int size();
            bool empty();
            
    };
    
    template<typename item>
    largest_heap<item>::largest_heap(){
        len=0;
        memset(heap,0,sizeof(heap));
    }
    
    template<typename item>
    void largest_heap<item>::push(item const &n){
        heap[++len]=n;
        int son=len,father=son/2;
        while(heap[son]>heap[father] && father>=1){
            swap(heap[son],heap[father]);
            son=father,father=son/2;
        }
    }
    
    template<typename item>
    void largest_heap<item>::pop(){
        swap(heap[1],heap[len]);
        heap[len--]=0;
        int father=1,son=2;
        while(son<=len){
            if(son<len && heap[son]<heap[son+1]) son++;
            if(heap[father]<heap[son]){
                swap(heap[father],heap[son]);
                father=son,son=father*2;
            }else break;
        }
    }
    
    template<typename item>
    item largest_heap<item>::top(){
        return heap[1];
    }
    
    template<typename item>
    int largest_heap<item>::size(){
        return len;
    }
    
    template<typename item>
    bool largest_heap<item>::empty(){
        return len;
    

    同时也可以支持自己编写的类,但须提供“<”或“>”的运算符重载,例如

    class T{
        private:
            int a;
        public:
            bool operator<(T const &type){
                return a<type.a;
            }
    };
    smallest_heap<T> heap;
    

    最后的总结
    我们现在所运用的C++,只是它的冰山一角,如果有与我同样爱好C++的,对运算符重载,lambda函数,类继承,函数重载,虚方法等感兴趣的,可以私信我,一起进步!

    番外中的番外
    推荐一个网站和一本书

    C语言中文网 c.biancheng.net

    《C++ Primer Plus》

    ----毕竟萌新,文笔不好,请多多包容

  • 2
    @ 2017-11-07 21:13:05

    一串蠕干倾情提供~qwq

    #include<iostream>
    #include<algorithm>
    using namespace std;
    int a[1000001]={0};
    int main()
    {
    int n=0,y=0,sum=0;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a,a+n);
    for(int j=1;j<=n-1;j++)
    {
    for(y=1;y<=n-j;y++)
    {
    a[y]+=a[y+1];
    a[y+1]=0;
    }
    sum+=a[1];
    sort(a,a+y);
    }
    cout<<sum;
    }
    
  • 1
    @ 2020-12-31 15:51:27

    emmm, 试了一下Java TreeMap,ac了,开始还担心内存溢出

    import java.util.Map.Entry;
    import java.util.Scanner;
    import java.util.TreeMap;
    import java.util.concurrent.atomic.AtomicInteger;
    
    public class Main {
        
        public static int getOne(TreeMap<Integer, AtomicInteger> fruitMap) {
            Entry<Integer, AtomicInteger> e = fruitMap.firstEntry();
            int first = e.getKey();
            e.getValue().decrementAndGet();
            if (e.getValue().get() == 0) {
                fruitMap.remove(e.getKey());
            }
            return first;
        }
        
        public static void main(String[] args) {
            
            TreeMap<Integer, AtomicInteger> fruitMap = new TreeMap<>();
            
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt();
            for (int i=0;i<n;i++) {
                int fruit = scanner.nextInt();
                fruitMap.putIfAbsent(fruit, new AtomicInteger());
                fruitMap.get(fruit).incrementAndGet();
            }
            scanner.close();
            if (n < 2) {
                System.out.println(0);
                return;
            }
            long total = 0;
            while (true) {
                int combine = getOne(fruitMap) + getOne(fruitMap);
                total += combine;
                if (fruitMap.isEmpty()) {
                    break;
                }
                fruitMap.putIfAbsent(combine, new AtomicInteger());
                fruitMap.get(combine).incrementAndGet();
            }
            System.out.println(total);
            
        }
    }
    
  • 1
    @ 2020-09-08 19:20:06

    #include <algorithm>
    using namespace std;

    int main(){
    int n;
    int arr[10000];
    cin >> n;
    for(int i = 0; i < n; i++){
    cin >> arr[i];
    }
    int sum = 0;
    sort(arr, arr + n);
    for(int i = 1 ; i < n; i++){
    arr[i] = arr[i] + arr[i-1];
    sum = sum + arr[i];
    sort(arr + i, arr + n);
    }

    cout << sum;
    }

  • 1
    @ 2020-03-18 00:31:14

    哈夫曼的套路

    #include<iostream>
    #include<queue> 
    using namespace std;
    
    priority_queue <int, vector<int>, greater<int> > PQ;
    
    int main() {
        int n , tmp, sum = 0;
        cin >> n;
        for (int i = 0 ; i < n ; ++i) {
            cin >> tmp;
            PQ.push(tmp);
        }
            
        while(PQ.size() > 1) {
            tmp = 0;
            for(int i = 0 ; i < 2 ; ++i) {
                tmp += PQ.top();
                PQ.pop();
            }
            
            sum += tmp;
            PQ.push(tmp);
        }
        
        cout << sum << endl;
        return 0;
    } 
    
  • 1
    @ 2020-03-01 12:10:50

    简单到炸!!

    P党

    var
      a:array[0..10001] of longint;
      n,i,j,s:longint;
    begin
      readln(n);
      for i:=1 to n do
        begin
          read(a[0]);
          j:=i-1;
          while a[0]>a[j] do
            begin
              a[j+1]:=a[j];
              dec(j);
            end;
          a[j+1]:=a[0];
        end;
      for i:=n-1 downto 1 do
        begin
          a[i]:=a[i+1]+a[i];
          s:=s+a[i];
          a[0]:=a[i];
          j:=i-1;
          while a[0]>a[j] do
            begin
              a[j+1]:=a[j];
              dec(j);
            end;
          a[j+1]:=a[0];
        end;
      writeln(s);
    end.
    
  • 1
    @ 2019-05-26 17:53:02
    #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;
    }
    
  • 1
    @ 2018-09-07 21:12:53

    第一次嘿qwq
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    int main()
    {
    int n,a,l[10000],add=0;
    scanf("%d",&n);
    for(a=0;a<n;++a)
    scanf("%d",l+a);
    for(a=1;a<n;++a){
    sort(l+a-1,l+n);
    l[a]+=l[a-1];
    add+=l[a];
    }
    printf("%d",add);
    }

  • 1
    @ 2018-06-02 16:01:32

    一个由数组到队列,在插入排序后返回队列的题(贪心)

    #include <iostream>
    #include <cstring> 
    #include <queue> 
    #include <algorithm> 
    using namespace std;
    int a[30010];
    queue <int> x;
    int main()
    {
        int i,n,s=0;
        cin>>n;
        for(i=1;i<=n;i++)
            cin>>a[i];
        sort(a+1,a+n+1); 
        for(i=1;i<=n;i++)
            x.push(a[i]);
        int y; 
        while(x.size()>1)
        {
            y=x.front();
            x.pop();
            y+=x.front();
            x.pop();
            s+=y;
            n=x.size()+1; 
            memset(a,0,sizeof(a));
            a[1]=y; 
            for(i=2;i<=n;i++)
            {
                 a[i]=x.front();
                 x.pop(); 
            } 
            sort(a+1,a+n+1); 
            for(i=1;i<=n;i++) 
                x.push(a[i]); 
        } 
        cout<<s<<endl; 
        return 0;
    }
    
    
  • 1
    @ 2017-08-07 23:57:38

    其实是一个哈夫曼树的裸题,我们只需要用一个小根堆来维护就可以了,具体操作如下:

    如果只要求求出最小化这个式子\(\sum_{i = 1}^{n}w_{i}l_{i}\)的值:

    • 我们可以用优先队列维护一个小根堆,先将所有的叶子结点放入小根堆。
    • 当堆中元素个数大于\(1\)时,每次取出堆中两个最小元素,它们同为一个结点的左右儿子,且它们的父亲结点(非叶结点)的权值为两个元素之和
    • 将两个叶子结点的父亲结点(非叶结点)的权值放回堆中
    • 循环往复,直至堆中元素个数小于等于\(1\)
    //  NOIP 2004 合并果子
    //  Copyright (c) 2017年 ZJYelizaveta. All rights reserved.
    #include <bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    inline int readIn() {
        int x = 0, f = 1;
        char ch = getchar();
        while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
        while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
        return x * f;
    }
    const int MAX_N = 10000 + 3;
    const int INF = 0x3f3f3f3f;
    int n;
    priority_queue< int, vector<int>, greater<int> > q;
    int ans;
    
    int main()
    {
    #ifdef DEBUG
        freopen("test.in", "r", stdin);
    #endif
        n = readIn();
        while (!q.empty()) q.pop();
        for (int i = 0; i < n; ++i) {
            int num = readIn();
            q.push(num);
        }
        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;
    }
    
  • 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-02-07 17:32:17

    解题思路:不断将最小的两个数相加。
    使用链式结构来储存数据
    需要删减数据,提高效率
    通过递归实现多次两个数相加
    基例:数据只有1个数的时候-输出结果。
    递归链:
    1.寻找最小的两个数
    2.将一个数变为两数之和
    3.将另一个数删去
    4.将剩余的数据代入函数

    代码比较长,有兴趣的话可以看一下:

    #include<iostream>
    using namespace std;
    typedef struct _node {
        int data;
        struct _node *next;
    }Node,*Ptr;
    void minpower(Ptr Head, int size) {//计算最小体力
        static int power = 0;
        if (size == 1)cout << power;
        else {
            int Min1=Head->next->data, Min2=Head->next->next->data;
            Ptr p = Head->next->next, M1 = Head->next, M2 = Head->next->next, _M2 = Head->next, _p = p;
            for (int i = 0; i < size-2; i++)//找出最小的两个值
            {
                p = p->next;
                if (Min1 >= Min2 && Min1 > p->data) {
                    Min1 = p->data;
                    M1 = p;
                }
                else if (Min2 >= Min1 && Min2 > p->data) {
                    Min2 = p->data;
                    _M2 = _p;
                    M2 = p;
                }
                _p = p;
            }
            M1->data = Min1 + Min2;//改变M1的值
            if (_M2->next->next)_M2->next = _M2->next->next;//删除M2
            else _M2->next = NULL;
            delete M2;
            power += Min1 + Min2;
            minpower(Head, size - 1);
        }
    }
    int main()
    {
        int N, num;
        Ptr Head = new Node, p = new Node, Last = p;
        cin >> N;
        Head->next = p;
        for (int i = 0; i < N; i++)//链式储存数据
        {
            Last->next = p;
            cin >> num;
            p->data = num;
            Last = p;
            p = new Node;
            Last->next = NULL;
        }
        delete p;
        minpower(Head, N);
        return 0;
    }
    
  • 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()表示*/

信息

ID
1097
难度
6
分类
贪心 点击显示
标签
递交数
23147
已通过
6144
通过率
27%
被复制
19
上传者