10954 - Add All

[brianfry713]

To get the minimum total cost, you should always add the two smallest numbers. You can accomplish that using a priority queue.

9 9 9 9 9 9
9 + 9 = 18, total cost = 18
9 9 9 9 18
9 + 9 = 18, total cost = 36
9 9 18 18
9 + 9 = 18, total cost = 54
18 18 18
18 + 18 = 36, total cost = 90
18 36
18 + 36 = 54, total cost = 144

[bgcsaif]

What should be output of single input

Code: Select all

1
87
0

And should I print new line after each case output?

[lighted]

There won't be input where N = 1. According to problem description N >= 2.

Each test case will start with a positive number, N (2 ? N ? 5000)

Sort array. Each time get sum of two smallest numbers then place new sum into array to preserve it sorted and add current sum to total cost.

[bgcsaif]

Thank you very much to get me out of my confusion. Sometimes over thinking makes one to think so complex that he forgets the simplest thing. I got Accepted! Thanks lighted

[tanvir cse]

why it time limit?????

Code: Select all

/*      TANVIR HASAN */

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <string>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <algorithm>
#include <iterator>
#include <bitset>

//#include <bits/stdc++.h>
using namespace std;

#define uu         first
#define vv         second
#define pb         push_back
#define mp         make_pair
#define LL         long long
#define inf        INT_MAX/3
#define mod        1000000007ll
#define PI         acos(-1.0)
#define linf       (1ll<<60)-1
#define FOR(I,A,B)  for(int I = (A); I < (B); ++I)
#define ALL(A)     ((A).begin(), (A).end())
#define set0(ar)   memset(ar,0,sizeof ar)
#define setinf(ar) memset(ar,126,sizeof ar)
#define vsort(v)   sort(v.begin(),v.end())
#define pii        pair<int,int>


template <class T> inline T bigmod(T p,T e,T M)
{
    LL ret = 1;
    for(; e > 0; e >>= 1)
    {
        if(e & 1) ret = (ret * p) % M;
        p = (p * p) % M;
    }
    return (T)ret;
}
template <class T> inline T gcd(T a,T b)
{
    if(b==0)return a;
    return gcd(b,a%b);
}
template <class T> inline T modinverse(T a,T M)
{
    return bigmod(a,M-2,M);
}



int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n,m,p;
    vector<int> cst;
    while(scanf("%d",&n)==1 && n)
    {

        vector<int> cst;
        FOR(i,0,n)
        {
            scanf("%d",&m);
            cst.pb(m);
        }
         m=0;
        while(cst.size()!=1)
        {

           vsort(cst);
           p=cst[0]+cst[1];
            cst.pb(p);
            m+=p;
            cst.erase(cst.begin(),cst.begin()+2);
        }
       // vsort(cst);
        cout<<m<<endl;


    }





    return 0;
}

[predicate]

if the size of the array is n, you sort the array n times, so the worst case run time of your program is O(n^2 lg(n)) which will be TLE for the given max size of n, which is 5000. You cannot sort the array every time you add two numbers. Think of a better approach which decreases the runtime of your algorithm.