10954 - Add All

[brianfry713]

Use a priority_queue.

[Hasselli]

Use a priority_queue.

I don't know what is this?

[brianfry713]

http://www.cplusplus.com/reference/stl/priority_queue/

[Hasselli]

Code: Select all

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int main(){
   int n;
   cin >> n;
   while (!n == 0){
		priority_queue<int> a;
		int b;
		int cost = 0;
		int sum = 0;
		if (n == 2){
			int c;
			cin >> b >> c;
			cout << b + c;
		}
		else{
			for (int i = 1; i <= n; i++){
				cin >> b;
				a.push(b);
			}
			for (int i = 3; i<= n; i++){
				sum += cost;
				cost += a.top();
				a.pop();
			}
			sum += cost;
			cout << sum << endl;
		}
		cin >> n;
   }
}

Why wrong?

[brianfry713]

Your algorithm is wrong and the result doesn't match the sample input.

Push the input onto the priority_queue.
Add the sum of the two smallest numbers to the cost, push the sum back on the queue. Repeat until there is only one number left on the queue.

[Hasselli]

Code: Select all

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int main(){
   int n;
   cin >> n;
   while (!n == 0){
      priority_queue<int> a;
      int b;
      int cost = 0;
      int sum = 0;
      if (n == 2){
         int c;
         cin >> b >> c;
         cout << b + c;
      }
      else{
         for (int i = 1; i <= n; i++){
            cin >> b;
            a.push(b);
         }
		 while (a.size() > 1){
			 b = a.top();
			 a.pop();
			 a.push(a.top() + b); 
			 a.pop();
		 }
		 cout << a.top() << endl;
      }
      cin >> n;
   }
}

Do you mean this?

[brianfry713]

No. That doesn't match the sample input. First read the two smallest elements from the priority_queue. Then add the sum to the cost and place the sum back on the priority_queue. Don't output the final sum that should be on the priority_queue, but the cost.

[Hasselli]

How to find two smallest?

[Hasselli]

error C2064: term does not evaluate to a function taking 2 arguments xutility

I got this error with this code:

Code: Select all

removed after AC

[brianfry713]

priority_queue< int, vector<int>, greater<int> > a;

[Hasselli]

Thank you very much Brian.

[sumon sarker]

I am getting wrong answer! Please give me some other sample input/output.........

[shuvrothpol1]

6
9 9 9 9 9 9
how can it possible that the answer is 144 ? The answer should be 180. Shouldn't it ? If I am wrong please inform me where is my mistake.Because, i got WA of it.Besides, I use bubble sort to solve the problem ..

[brianfry713]

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

[CyberPunk]

Code: Select all

#include <stdio.h>
#include <string.h>
void sort(long long int array[], long long int length)
{
    long long int i,j,count,pos,min[10000][2];

    for(i=0;i<length;i++) {
        min[i][1]=0;
    }
    for(i=0;i<length;i++) {
        count=0;
        for(j=0;j<length;j++) {
            if(array[i]<array[j]) count++;
        }
        pos=++min[count][1];
        min[count+pos-1][0]=array[i];
    }
    for(i=0;i<length;i++) array[i]=min[i][0];
}

int main()
{
    long long int num[10000],N,i,j,k,l,sum,temp;
    while(scanf("%lld",&N)==1 && N) {
        i=0;
        for(i=0;i<N;i++) scanf("%lld",&num[i]);
        sort(num,N);
        sum=0,temp=0;
        if(N==1) printf("%lld\n",num[0]);
        else {
            for(i=N-1;i-1>=0;i--) {
                temp=num[i-1]+num[i];
                sum+=temp;
                num[i-1]=temp;
                num[i]=0;
                sort(num,N);
            }

            printf("%lld\n",sum);
        }
        memset(num,0,sizeof(num));
    }
    return 0;
}

why do i get TLE? any suggestions?