题解

532 条题解

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

  • 0
    @ 2018-06-11 10:40:20

    #include<iostream>
    #include<cstdio>
    #include<queue>
    using namespace std;
    priority_queue <int,vector<int>,greater<int> >q;
    int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
    int a;
    scanf("%d",&a);
    q.push(a);
    }
    int ans=0;
    while(1){
    int a=q.top();
    q.pop();
    if(q.empty())break;
    else{
    int b=q.top();
    q.pop();
    ans+=a+b;
    q.push(a+b);
    }
    }
    printf("%d",ans);
    return 0;
    }

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

  • 0
    @ 2018-05-29 19:19:14

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

信息

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