题解

536 条题解

  • 10
    @ 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;
    }
    
    
  • 8
    @ 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》

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

  • 1
    @ 2024-11-30 19:04:19

    不难发现此题的最优策略就是:每次取出最小的两个数,相加,放入序列,重复此操作。

    那么如何维护每次最小的两个数呢?这里首先排除掉sort,因为一次sort并不满足上述

    每次取出最小的两个数

    如果每次操作都是用一次sort的话,时间复杂度是巨大的,故不能AC

    那有什么办法能在 \( O(n) \) 的时间复杂度之内,处理完维护每次取出最小的两个数呢?

    既然静态维护无法,就动态维护

    动态维护,最小……

    小根堆!!!

    于是就有了水代码了

    ACcode

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    
    priority_queue <int, vector <int>, greater <int>> q; 
    
    int main()
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            int num; cin >> num;
            q.push(num);
        }
        int ans = 0;
        while (q.size() > 1)
        {
            int t1 = q.top();
            q.pop();
            int t2 = q.top();
            q.pop();
            ans += t1 + t2;
            q.push(t1 + t2);
        }
        cout << ans << endl;
        return 0;
    }
    
  • 1
    @ 2021-08-28 12:13:48
    #include<bits/stdc++.h>
    using namespace std;
    
    int k,x,num,n1,n2,a1[30001],a2[30001],t[20001],w,sum;
    int main()
    {
        cin>>num;
        memset(a1,127/3,sizeof(a1));
        memset(a2,127/3,sizeof(a2));
        for(int i=1; i<=num; i++){
            cin>>x;
            t[x]++;
        }
        for(int i=1; i<=20000; i++){
            while(t[i]){
                t[i]--;
                a1[++n1]=i;
            }
        }
        int i=1,j=1;
        k=1;
        while (k<num)
        {
            if(a1[i]<a2[j]){
                w=a1[i];
                i++;
            }
            else{
                w=a2[j];
                j++;
            }
            if(a1[i]<a2[j]){
                w+=a1[i];
                i++;
            }
            else{
                w+=a2[j];
                j++;
            }
            a2[++n2]=w;
            k++;
            sum+=w;
        }
        cout<<sum;
        return 0;
    }
    
  • 1
    @ 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;
    }
    
  • 0
    @ 2024-10-04 09:46:57

    今天给大家介绍一种特别好用的排序队列:堆
    分为大根堆:priority_queue<类型>队列名
    小根堆:priority_queue<类型,vector<类型>,greater<类型> >队列名
    根据以上知识便能轻而易举的写出如下的AC代码
    #include<iostream>
    #include<queue>
    #define int long long
    using namespace std;
    int n,sum;
    priority_queue<int,vector<int>,greater<int> >pq;
    signed main(){
    cin >> n;
    while(n--){
    int x;cin >> x;
    pq.push(x);
    }
    while(pq.size() > 1){
    int x = pq.top();
    pq.pop();
    int y = pq.top();
    pq.pop();
    sum += x + y;
    pq.push(x + y);
    }
    cout << sum;
    return 0;
    }

  • 0
    @ 2024-09-15 20:30:35

    ···cpp
    int

  • 0
    @ 2024-06-01 16:09:13

    优先队列。。。

    #include<bits/stdc++.h>
    using namespace std;
    int n,a,b,ans;
    priority_queue<int,vector<int>,greater<int> >q;//重载线性容器,把大数往下推 【两个大于号之间一定要加空格】
    int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a),q.push(a);
        while(q.size()>1){
            a=q.top();
            q.pop();
            b=q.top();
            q.pop();
            ans+=a+b;//加上体力
            q.push(a+b);//又堆了一堆
        }
        printf("%d",ans);
        return 0;
    }
    
  • 0
    @ 2022-07-08 12:45:49

    #哈夫曼编码
    python3
    对于每一堆果子,我们可能要移动多次。
    所以抽象出来就是求一个*最优二叉树*
    即*节点带权路径长度*和最小的二叉树

    n=int(input().strip())
    s = list(map(int, input().split()))
    cnt = 0
    
    while len(s)>1:
        s.sort()  
            #对数据从小到大排序
        s[1] = s[0]+s[1]  
            #合并最小的两个,作为一个新的节点
        s.pop(0)
        cnt += s[0]
            #计算带权路径
    
    print(cnt)
    
  • 0
    @ 2022-06-09 20:52:07

    优先队列无敌!

    #include <iostream>
    #include <queue>
    using namespace std;
    int main(int argc, char** argv) {
        priority_queue<int,vector<int>, greater<int>> que;
        int a;
        cin>>a;
        for(int i=0;i<a;i++){
            int b;
            cin>>b;
            que.push(b);
        }
        int e=0;
        while(1){
            int x=que.top();
            que.pop();
            int y=que.top();
            que.pop() ;
            int s=x+y;
            e+=s;
            que.push(s);
            if(que.size()==1){
                break;
            }
        }
        cout<<e<<endl;
        return 0;
    }
    
  • 0
    @ 2022-05-06 20:46:24

    我c,试了**2遍**,过了
    小样,不开long long 见祖宗
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <queue>
    using namespace std;
    priority_queue<int,vector<int>,greater<int> > str;
    int n,Ans,tot,num;
    void init(){
    int x;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
    cin >> x;
    str.push(x);
    }
    }
    int main(){
    init();
    while(str.empty() == false)
    {
    tot += str.top();
    str.pop(); num++;
    if(num % 2 == 0)
    {
    Ans += tot;
    str.push(tot);
    tot = 0;
    }
    }
    cout << Ans;
    return 0;
    }

  • 0
    @ 2022-03-03 20:01:58

    此题推荐用优先队列:

    #include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        priority_queue<int,vector<int>,greater<int> > q;
        int n,i,x,s,y;
        long long he=0;
        cin>>n;
        for(i=1;i<=n;i++)
        {
            cin>>x;
            q.push(x);
        }
        for(i=1;i<=n-1;i++)
        {
            s=q.top();
            q.pop();
            y=q.top();
            q.pop();
            he=he+s+y;
            q.push(s+y);
        }
        cout<<he;
        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-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);
            
        }
    }
    
  • 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-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;
    }

  • 0
    @ 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;
    } 
    
  • 0
    @ 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.
    
  • 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))
    
    

信息

ID
1097
难度
6
分类
贪心 点击显示
标签
递交数
23909
已通过
6333
通过率
26%
被复制
41
上传者