Page 1 of 6

Posted: 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...

Code: Select all

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

Posted: Sun Oct 30, 2005 1:08 am
Try this test case

5
2 2 2 2 3

Posted: 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

Posted: 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

Posted: Sun Oct 30, 2005 3:13 am
OH........why was I that stupid...>.<||

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

### Oh my god...

Posted: 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-

Posted: Sun Oct 30, 2005 4:22 am
You can solve this problem in very few lines with a min priority queue.

### thx

Posted: 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-

Posted: 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...

Posted: 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.

Posted: 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 ?

Posted: Sun Oct 30, 2005 6:52 am
I used a priority queue (implemented by heap) and the program runs 0.2s

Posted: Sun Oct 30, 2005 12:58 pm
Also you can use multiset

Posted: Sun Oct 30, 2005 1:14 pm
tywok wrote:Also you can use multiset
thank you