It's so idiot...
If it add
Code: Select all
memset(ans,0,sizeof(ans));
Moderator: Board moderators
Code: Select all
memset(ans,0,sizeof(ans));
Code: Select all
#include <stdio.h>
class ELEMENT
{
public:
int value;
ELEMENT *left,*right,*daddy;
ELEMENT()
{
left=0;
right=0;
daddy=0;
value=0;
}
};
class TREE
{
public:
void Put(ELEMENT *where_to_put_it,ELEMENT *branch)
{
if((where_to_put_it->value)>(branch->value))
{
if((branch->right)!=0)
{
Put(where_to_put_it,(branch->right));
}
else
{
branch->right=where_to_put_it;
where_to_put_it->daddy=branch;
}
}
else
{
if((branch->left)!=0)
{
Put(where_to_put_it,(branch->left));
}
else
{
branch->left=where_to_put_it;
where_to_put_it->daddy=branch;
if(min->value>=where_to_put_it->value)
{
min=where_to_put_it;
}
}
}
}
void FindMin(ELEMENT *subtree)
{
delete min;
ELEMENT *horse;
horse=subtree;
while(horse->left!=0)
horse=horse->left;
min=horse;
}
ELEMENT *root;
ELEMENT *min;
int number_of_elements;
TREE()
{
root=0;
number_of_elements=0;
}
TREE(int in)
{
root=0;
number_of_elements=0;
Add(in);
}
void Add(int in)
{
ELEMENT *add;
add=new ELEMENT;
add->value=in;
if(root!=0)
{
Put(add,root);
}
else
{
root=add;
min=add;
}
number_of_elements++;
}
int Min(void)
{
return (*min).value;
}
void RemoveMin()
{
if(number_of_elements==1)
{
root=0;
}
else
if(root==min)
{
root=root->right;
FindMin(root);
}
else
{
if(min->right!=0)
{
min->daddy->left=min->right;
min->right->daddy=min->daddy;
FindMin(min->right);
}
else
{
min->daddy->left=0;
min=min->daddy;
}
}
number_of_elements--;
}
};
int computeExp(TREE *tree)
{
int out=0, help=0;
while(tree->number_of_elements>1)
{
help=tree->Min();
tree->RemoveMin();
help+=tree->Min();
tree->RemoveMin();
out+=help;
tree->Add(help);
help=0;
}
return out;
}
int main()
{
short in=1;
int b;
while(in>0)
{
TREE tree;
scanf("%d",&in);
if (in>0)
{
for (int a=(in-1);a>=0;a--)
{
scanf("%d",&b);
tree.Add(b);
}
in=1;
printf("%d\n",computeExp(&tree));
}
delete &tree;
}
return 0;
}
You probably should have used 'int' instead of 'short' on line 143.p.cc: In function ‘int main()’:
p.cc:149: warning: format ‘%d’ expects type ‘int*’, but argument 2 has type ‘short int*’
Don't reinvent the wheel, use the existing code when possible. In this problem, for example, you could've used STL's std::set instead of your own tree.-I use my own defined structure(class) and work with pointers.
Code: Select all
5
10 20 30 40 50
7
100 9999 2355 7777 8888 2345 1234
10
12 45 23 67 23 9 56 234 45 65
12
9999 9998 88888 0 88888 88898 66666 55555 4324 2356 5676 9988
6
9 9 9 9 9 9
40
99999 99999 99999 99999 99999 99999 99999 99999 99999 99999
99998 99998 99998 99998 99998 99998 99998 99997 99997 19998
99995 99995 99995 99995 99995 99995 99995 99995 99995 99995
59995 99995 99595 99995 39995 99995 99995 99995 99995 99995
0
Code: Select all
330
76443
1612
1221996
144
20476861
Code: Select all
#include<stdio.h>
long int partition(long int m,long int p);
void interchange(long int i,long int j);
void quicksort(long int p,long int q);
long int a[5500],num;
int main()
{
long int carry,sum,total,i;
while(scanf("%ld",&num)==1)
{
if(num==0)
break;
for(i=1;i<=num;i++)
scanf("%ld",&a[i]);
quicksort(1,num);
carry=a[1];
total=0;
for(i=2;i<=num;i++)
{
sum=carry+a[i];
a[i]=sum;
quicksort(i,num);
carry=a[i];
total+=sum;
}
printf("%ld\n",total);
}
return 0;
}
void quicksort(long int p,long int q)
{ long int j;
if(p<q)
{
j=partition(p,q+1);
quicksort(p,j-1);
quicksort(j+1,q);
}
}
long int partition(long int m,long int p)
{
long int v,i,j,temp;
v=a[m];i=m;j=p;
do
{ do
{
i=i+1;
}while(a[i]<v);
do
{
j=j-1;
}while(a[j]>v);
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}while(i<j);
a[m]=a[j];
a[j]=v;
return j;
}
Thanks for your hint. I start to appreciate the clever cover of this problem.zobayer wrote:Hello,
This problem is commonly known as Huffman Coding (http://en.wikipedia.org/wiki/Huffman_coding)
I used simply a priority_queue to solve this one.
Code: Select all
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int n;
cin >> n;
while (!n == 0){
int a[5001];
int cost = 0;
int sum = 0;
for (int i = 1; i <= n; i++){
cin >> a[i];
}
if (n == 2)
cout << a[1] + a[2];
else{
sort(a, a + n);
cost = a[1] + a[2];
for (int i = 3; i<= n; i++){
sum += cost;
cost += a[i];
}
sum += cost;
cout << sum;
}
cin >> n;
}
return 0;
}
It's not important.I gave wrong answers in my own computer.brianfry713 wrote:You're not printing any newlines.
brianfry713 wrote:The proper placement of newlines are important if you want to get AC.
Code: Select all
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int n;
cin >> n;
while (!n == 0){
int a[5001];
int cost = 0;
int sum = 0;
for (int i = 1; i <= n; i++){
cin >> a[i];
}
if (n == 2)
cout << a[1] + a[2];
else{
sort(a, a + n);
cost = a[1] + a[2];
for (int i = 3; i<= n; i++){
sum += cost;
cost += a[i];
}
sum += cost;
cout << sum << endl;
}
cin >> n;
}
return 0;
}