10954 - Add All

[taha]

there exist priority queue implemented in STL ???

[Emilio]

Yes. http://www.sgi.com/tech/stl/

[taha]

thanks for ur reply.
but one more isssue: implementing it using heap has no more advantage than this one, in speed or whatever ??

[misof]

The STL priority_queue is implemented as a heap in a vector<T>.

[Larry]

Are there any trick cases? I also used a heap implementation..

[Larry]

Nevermind, I missed the N=0 for ending.. I'm an idiot.

[Jeff]

I don't know why I got WA...
help me...please.....

Code: Select all

#include<stdio.h>
int n,all,que[5002];
int add(int in)
{
	int index;
	index=all;
	all++;
	while(index>0)
	{
		if(in<que[(index-1)/2])
		{
			que[index]=que[(index-1)/2];
			index=(index-1)/2;
		}
		else
			break;
	}
	que[index]=in;
	return 0;
}
int del()
{
	int index=0;
	all--;
	while(index<=(all-2)/2)
	{
		if(que[all]>que[index*2+1])
		{
			que[index]=que[index*2+1];
			index=index*2+1;
		}
		else if(index*2+3<=all && que[all]>que[index*2+2])
		{
			que[index]=que[index*2+2];
			index=index*2+2;
		}
		else
			break;
	}
	que[index]=que[all];
	return 0;
}
int main()
{
	int k,i,out;
	while(scanf("%d",&n)==1 && n!=0)
	{
		all=out=0;
		for(i=0;i<n;i++)
		{
			scanf("%d",&k);
			add(k);
		}
		while(all>1)
		{
			k=que[0];
			del();
			k+=que[0];
			del();
			add(k);
			out+=k;
		}
		printf("%d\n",out);
	}
	return 0;
}

[Martin Macko]

Try this input:

Code: Select all

14
1 8 2 4 7 89 5 8 74 2 6 8 5 47
0

My AC's output is:

Code: Select all

717

[Jeff]

Thanks~
I got AC...

[Nazmul Quader Zinnuree]

I'm getting WA using priority queue (and long long data type)

My Input:

Code: Select all

5
2 2 2 2 3
5
1 1 1 1 1
14
1 8 2 4 7 89 5 8 74 2 6 8 5 47
4
1 2 3 4
5
1 2 3 4 5
2
1 1
0

My Output:

Code: Select all

26
12
717
19
33
2

These are right, I think. Somebody, give me some more I/O, plz...
Thanks...

[Nazmul Quader Zinnuree]

OK, Noboby is giving me some I/O that i wanted in another mail.

Now, would you just plz run my code, and say where I'm wrong!!!

Btw, I did not want to send my code. But, no way....

Code: Select all

Code removed after AC

It matches the above test case and many other that I imagine.

[Martin Macko]

OK, Noboby is giving me some I/O that i wanted in another mail.

Now, would you just plz run my code, and say where I'm wrong!!!

Not working for this one:

Code: Select all

8
40952 13521 6223 42589 93489 22376 78730 38792
0

My AC's output:

Code: Select all

899661

[Martin Macko]

My Output:

Code: Select all

26
12
717
19
33
2

Yes, this output is correct... In the other thread (where you've posted your code) I've just posted a case your code doesn't work on.

[Nazmul Quader Zinnuree]

The bug was in my extract_min() function. AC now.
Thanks to Martin Macko

[tom76925]

I couldn't find out what's wrong in my code
I test all the data above and the answer was correct
but when I submit on UVa I got WA
could anyone can help me please... thank you very much~

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#define SWAP(x,y) {int t; t = x; x = y; y = t;}

void createheap(int[],int num);
void heapsort(int[],int num);
void addheap(int number[],int addnum,int num);

int main(void) {
    int number[5000+1],ans[5000+1]={0};
    int i,num,m,count[3],k,answer=0;

    scanf("%d",&num);
    while(num!=0){
		for(i=1;i<=num;i++){
			scanf("%d",&number[i]);
		}

		createheap(number,num);

		m=num;
		k=1;
		while(m>1){

			SWAP(number[1], number[m]);
			count[0]=number[m];
			m--;
			heapsort(number,m);

			SWAP(number[1], number[m]);
			count[1]=number[m];
			m--;
			heapsort(number,m);

			count[2]=count[0]+count[1];
			ans[k]=count[2];
			k++;

			m++;
			addheap(number,count[2],m);
		}

		i=1;
		while(ans[i]!=0){
			answer+=ans[i];
			i++;
		}
		printf("%d\n", answer);
		answer=0;
		scanf("%d",&num);
	}
    return 0;
}

void createheap(int number[],int num) {
    int i, s, p;
    int heap[5000+1] = {0};

    for(i = 1; i <= num; i++) {
        heap[i] = number[i];
        s = i;
        p = i / 2;
        while(s >= 2 && heap[p] > heap[s]) {
            SWAP(heap[p], heap[s]);
            s = p;
            p = s / 2;
        }
    }

    for(i = 1; i <= num; i++)
        number[i] = heap[i];

}

void addheap(int number[],int addnum,int num) {
	int s, p;

	number[num]=addnum;
	s = num;
	p = num / 2;
	while(s >= 2 && number[p] > number[s]) {
		SWAP(number[p], number[s]);
		s = p;
		p = s / 2;
	}
}

void heapsort(int number[],int num) {
    int p, s;

	p = 1;
	s = 2 * p;
	while(s <= num) {
		if(s < num && number[s+1] < number[s])
			s++;
		if(number[p] <= number[s])
			break;
		SWAP(number[p], number[s]);
		p = s;
		s = 2 * p;
	}
}