题解

520 条题解

  • 13
    @ 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;
    }
    
    
  • 5
    @ 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;
    }
    
  • 3
    @ 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);
    }

  • 2
    @ 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;
    }
    
  • 2
    @ 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;
    }
    
    
  • 2
    @ 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;
    }
    
  • 2
    @ 2017-03-03 14:32:17

    将数组由小到大排序之后,每次都取前两个的和,按大小插入到剩下的数组中,保证剩下的数组也是从小到达排序的。
    注意的是每次取和之后剩下数组的起始位置就往后挪一位。
    java代码:
    import java.util.*;
    import java.io.*;
    public class tanxin {
    public static void main(String[]args)throws IOException{
    Scanner input=new Scanner(System.in);
    int n=input.nextInt();
    int[]s=new int[n];
    int temp,j,sum=0;
    for(int i=0;i<n;i++)
    s[i]=input.nextInt();
    if(n==1)
    {
    System.out.println(s[0]);
    return;
    }

    Arrays.sort(s); //
    for(int i=0;i<n-1;i++)
    {
    temp=s[i]+s[i+1];
    sum+=temp;
    for( j=i+1;j<n;j++)
    {
    if(s[j]<=temp)
    s[j-1]=s[j];
    else
    break;
    }
    s[j-1]=temp;

    }
    System.out.println(sum);
    }
    }

  • 1
    @ 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;
    }
    
  • 1
    @ 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;
    }
    
    
  • 1
    @ 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;
    }
    //函数实现区
    
  • 1
    @ 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
    
  • 1
    @ 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;
    }

  • 1
    @ 2018-06-03 21:19:19

    简单贪心
    主要算法:
    每次合并最小值和次小值
    然后进行删除
    附代码
    cpp
    #include<iostream>
    using namespace std;
    const int num = 10005;
    int apple[num];
    int ans = 0;
    int main() {
    int n;
    cin >> n;
    for(int i = 0;i < n;i++)
    cin >> apple[i];
    while(n > 1) {
    int min1 = 0,min2 = 1; // 查找最小值和次小值
    if(apple[min1] > apple[min2])
    swap(min1,min2);
    for(int i = 2;i < n;i++) {
    if(apple[i] < apple[min1]) {
    min2 = min1;
    min1 = i;
    }
    else if(apple[i] < apple[min2])
    min2 = i;
    }
    // 将最小值那个位置的数据修改为相加后的值
    // 另外将次小值那个位置的数据修改为appl[n-1]的值
    // 这样在n--时不会丢失数据
    if(min1 == n - 1) swap(min1,min2);
    int t = apple[min1] + apple[min2];
    ans += t;
    apple[min1] = t;
    apple[min2] = apple[n - 1];
    n--;
    }
    cout << ans;
    return 0;
    }

  • 1
    @ 2018-04-21 14:20:43

    用set容器自动排序的特点可以实现

    #include<cstdio>
    #include<iostream>
    #include<set>
    #include<algorithm>
    using namespace std;
    multiset<long long>aa;
    int main(){
    long long n,i,a,b,c,sum=0;
    multiset<long long>::iterator it;
    cin>>n;
    for(i=1;i<=n;i++) {scanf("%lld",&a); aa.insert(a);}
    while(aa.size()!=1){
    it=aa.begin();
    sum+=*it;
    b=*it;
    aa.erase(it);
    it=aa.begin();
    c=*it;
    sum+=c;
    aa.erase(it);
    aa.insert(b+c);

    }
    printf("%lld",sum);
    return 0;
    }

  • 1
    @ 2018-03-24 10:06:54

    分享下堆的做法
    get()是取出小根堆的根节点
    put()是在堆中加入一个元素
    效率很高

    状态 耗时 内存占用

    #1 Accepted 12ms 364.0 KiB
    #2 Accepted 3ms 384.0 KiB
    #3 Accepted 4ms 368.0 KiB
    #4 Accepted 4ms 384.0 KiB
    #5 Accepted 7ms 360.0 KiB
    #6 Accepted 8ms 376.0 KiB
    #7 Accepted 7ms 364.0 KiB
    #8 Accepted 7ms 372.0 KiB
    #9 Accepted 4ms 384.0 KiB
    #10 Accepted 5ms 372.0 KiB

    #include<bits/stdc++.h>
    int a[20005],len;
    using namespace std;
    int get()
    {
        int min,now,son,le,ri,t;
        min=a[1];
        a[1]=a[len];
        a[len]=0;
        len--;
        now=1;
        while(now*2<=len)
        {
            le=now*2;
            ri=now*2+1;
            if (ri>len)
                son=le;
            else
            {   
                if (a[le]<a[ri])
                    son=le;
                else
                    son=ri;
            }   
            if (a[now]>a[son])
            {
                t=a[now];
                a[now]=a[son];
                a[son]=t;
                now=son;
            }
            else
                break;
        }
        return min;
    }
    void put(int x)
    {
        int now,fa,t;
        len++;
        a[len]=x;
        now=len;
        fa=now/2;
        while (now!=1)
        {
            if (a[now]<a[fa])
            {
                t=a[now];
                a[now]=a[fa];
                a[fa]=t;
                now=fa;
                fa=now/2;
            }
            else
                break;
        }
    }
    int main()
    {
        int n,ans;
        int i,j,tmp,x,y;
        cin>>n;
        len=1;
        ans=0;
        cin>>a[1];
        for(i=2;i<=n;i++)
        {   
            cin>>tmp;
            put(tmp);
        }
        while (len>1)
        {
            x=get();
            y=get();
            ans=ans+x+y;
            put(x+y);
        }
        cout<<ans;
        return 0;
    }
    
    
  • 1
    @ 2017-11-07 17:12:59

    再发个简单的优先队列
    #include<iostream>
    #include<queue>
    using namespace std;
    priority_queue<int,vector<int>,greater<int> >p;//小的优先出的
    int n;
    int a,sum;
    int main()
    {
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    cin>>a;
    p.push(a);
    }
    while(p.size()!=1)
    {
    int d=p.top(); p.pop();
    int b=p.top(); p.pop();
    int c=d+b; p.push(c);
    sum+=c;
    }
    cout<<sum;
    return 0;
    }

  • 1
    @ 2017-11-06 21:27:53

    没错此题是裸题
    就是优先队列
    而已

    #include<iostream>
    #include<queue>
    using namespace std;
    priority_queue<int,vector<int>,greater<int> >q;
    int n;
    int main()
    {
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    int tmp;
    cin>>tmp;
    q.push(tmp);    
    }   
    int ans=0;
    for(int i=1;i<n;i++)
    {
        int x=q.top();
        q.pop();
        int y=q.top();
        q.pop();
        int tmp2=x+y;
        ans+=tmp2;
        q.push(tmp2);
        
    }
    cout<<ans;
    
        
    }    
    
  • 1
    @ 2017-07-16 14:55:33

    var
    a,b:array[1..215000000]of integer;
    n,i,j,s,m,f:longint;
    begin
    readln(n);for i:=1 to n do begin read(a[i]);inc(b[a[i]]);end;
    while n>1 do begin
    f:=0;i:=1;m:=0;
    while f<2 do begin
    while b[i]>0 do begin inc(f);inc(s,i);inc(m,i);dec(b[i]);end;
    inc(i);
    end;
    inc(b[m]);dec(n);
    end;
    writeln(s);
    end.

  • 0
    @ 2020-02-09 11:08:58

    #include <cstdio>
    #include <queue>
    #define int long long
    using namespace std;
    queue <int> q1;
    queue <int> q2;
    int to[100005];
    void read(int &x){
    int f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;}
    signed main() {
    int n;read(n);
    for (int i = 1; i <= n; ++i) {
    int a;read(a);to[a]++;}
    for (int i = 1; i <= 100000; ++i) {
    while(to[i]) {to[i] --;q1.push(i);}}
    int ans=0;
    for (int i=1;i<n;++i){
    int x,y;
    if((q1.front()<q2.front()&&!q1.empty())||q2.empty()){
    x=q1.front();q1.pop();}
    else{x=q2.front();q2.pop();}
    if((q1.front()<q2.front()&&!q1.empty())||q2.empty()){
    y=q1.front();q1.pop();}
    else{y=q2.front();q2.pop();}
    ans+=x+y;q2.push(x + y);}
    printf("%lld" ,ans);
    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
分类
贪心 点击显示
标签
递交数
22478
已通过
5942
通过率
26%
被复制
9
上传者