题解

523 条题解

  • 12
    @ 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;
    }
    
    
  • 4
    @ 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;
    }
    
  • 2
    @ 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
    @ 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-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;
    }
    
  • 1
    @ 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);
    }
    }

  • 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()表示*/

  • 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;
    }

信息

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