Page 6 of 6
Re: 10954 - Add All
Posted: Wed Oct 01, 2014 11:13 pm
by 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
Re: 10954 - Add All
Posted: Fri Oct 03, 2014 11:05 am
by bgcsaif
What should be output of single input
And should I print new line after each case output?
Re: 10954 - Add All
Posted: Fri Oct 03, 2014 11:47 am
by 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.
Re: 10954 - Add All
Posted: Fri Oct 03, 2014 1:22 pm
by 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
10954
Posted: Thu May 28, 2015 12:34 pm
by 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;
}
Re: 10954
Posted: Sun Jun 07, 2015 8:09 pm
by 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.