10954 - Add All

Deno · Post by **Deno** » Sun Oct 30, 2005 12:55 am

I absolutely no idea why I am getting a WA.
I got WA even after changing uint to double, sorting the numbers...

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
	typedef unsigned int uint;
	int N;
	while(cin>>N && N!=0) {
		vector<uint> table(N);
		for (N--;N!=-1;--N)
			cin>>table[N];
		sort(table.begin(), table.end());
		uint total=table[0]*(table.size()-1);
		for (vector<uint>::size_type z=1; z<table.size(); z++) {
			total+=table[z]*(table.size()-z);
		}
		cout<<total<<endl;
	}
}

mf · Post by mf » Sun Oct 30, 2005 1:08 am

Try this test case

5
2 2 2 2 3

Deno · Post by **Deno** » Sun Oct 30, 2005 2:41 am

My program outputs 29 for that test case.

2+2=4
4+2=6
6+2=8
8+3=11

4+6+8+11=29

tywok · Post by **tywok** » Sun Oct 30, 2005 2:46 am

It should be

2 + 2 = 4
2 + 2 = 4
3 + 4 = 7
4 + 7 = 11

So, it is 4 + 4 + 7 + 11 = 26

Deno · Post by **Deno** » Sun Oct 30, 2005 3:13 am

OH........why was I that stupid...>.<||

Thank you sooooo much~~
I got AC now!!

valfiros · Post by **valfiros** » Sun Oct 30, 2005 4:05 am

Oh my god...I did absolutely same mistake...
(and got WA over 20 time, about 4 hours, saying "what the @%^"...)
thx alotttt!

-JSKim-

Bj · Post by Bj » Sun Oct 30, 2005 4:22 am

You can solve this problem in very few lines with a min priority queue.

valfiros · Post by **valfiros** » Sun Oct 30, 2005 5:15 am

yup, in first time, i used quick sort & insertion sort, but TLE...

and i used priority_queue (stl) and got AC.

THX alot!!

-JSKim/valfiros-

jan_holmes · Post by **jan_holmes** » Sun Oct 30, 2005 5:28 am

why :
5
2 2 2 2 3

the output :
2+2 = 4
2+2 = 4
4+3 = 7
7+4 = 11

4+4+7+11 = 26

why ??? could anyone explain it?? Thx...

shamim · Post by **shamim** » Sun Oct 30, 2005 6:03 am

Another way of staing the problem is ,
add two numbers from the list, add the result to the cumulative cost, remove the two numbers from the list and insert the sum to the list.
The answer will be the minimum cumulative value obtainable.

so,
2 2 2 2 3 -> (2+2=4)
4 2 2 3 -> (2+2=4)
4 4 3 ->(4+3=7)
7 4->(7+4=11)
11

and
4 +4 + 7 + 11 = 26.

SRX · Post by **SRX** » Sun Oct 30, 2005 6:13 am

shamim wrote:Another way of staing the problem is ,
add two numbers from the list, add the result to the cumulative cost, remove the two numbers from the list and insert the sum to the list.
The answer will be the minimum cumulative value obtainable.

so,
2 2 2 2 3 -> (2+2=4)
4 2 2 3 -> (2+2=4)
4 4 3 ->(4+3=7)
7 4->(7+4=11)
11

and
4 +4 + 7 + 11 = 26.

Is this problem like huffman

I use like insert and got ac 3.xxx seconds
What method can run faster ?

Deno · Post by **Deno** » Sun Oct 30, 2005 6:52 am

I used a priority queue (implemented by heap) and the program runs 0.2s

tywok · Post by **tywok** » Sun Oct 30, 2005 12:58 pm

Also you can use multiset

SRX · Post by **SRX** » Sun Oct 30, 2005 1:14 pm

tywok wrote:Also you can use multiset

thank you

I need to learn more stl

Tamagodzi · Post by **Tamagodzi** » Mon Oct 31, 2005 3:02 am

an array is enough

first solver under 0.1 s with scanf ^^