use priority_queue <unsigned int>!!!!

Posted by

Dan.hu 3 Feb 2007 13:07

Re: use priority_queue <unsigned int>!!!!

With 1 Mb memory limit? :-)

Re: use priority_queue <unsigned int>!!!!

AC now:)

*Edited by author 11.02.2007 15:03*

Re: use priority_queue <unsigned int>!!!!

You should store in queue n/2 +1 numbers

Re: use priority_queue <unsigned int>!!!!

I can't understand you... How I can do it?

Re: use priority_queue <unsigned int>!!!!

At first push n/2+1 numbers then do this

1 read next number

2 push it to queue

3 pop biggest element

4 goto 1

At the end use 2 or 1 top elements for answer

Re: use priority_queue <unsigned int>!!!!

Thank you very much!!! I got AC!

Re: use priority_queue <unsigned int>!!!!

I use priority queue as you said,but still MLE#7.Maybe I'm wrong,here is my code:

#include<iostream>

using namespace std;

#include<queue>

int main()

{std::priority_queue<int>pr;

int n,i,a;

cin>>n;

for(i=1;i<=n/2+1;i++)

{cin>>a;

pr.push(a);

}

i=n/2+2;

while(i<=n){

cin>>a;

pr.push(a);i++;

pr.pop();

}

if(n%2!=0)

cout<<pr.top()<<".0"<<endl;

else

{a=pr.top();

pr.pop();

if(a%2+pr.top()%2==2)

cout<<a/2+pr.top()/2+1<<".0"<<endl;

else

if(a%2+pr.top()%2==0)

cout<<a/2+pr.top()/2<<".0"<<endl;

else

if(a%2+pr.top()%2==1)

cout<<(a/2+pr.top()/2)<<".5"<<endl;

}

return 0;

}

Thank!!!

*Edited by author 18.09.2007 19:59*

try *_heap (+)

Posted by

ASK 28 Feb 2010 18:29

int v[250000/2+3];

for(; i < n/2+1; ++i) cin >> v[i];

make_heap(v,v+n/2+1);

for(; i < n; ++i){

cin >> v[n/2+1];

push_heap(v,v+n/2+2);

pop_heap(v,v+n/2+2);

}

BTW(1), there is no need for "unsigned" since input is less than 2^31-1

BTW(2), there is no need to avoid "double a" in calculation and output of the the final answer:

cout << setprecision(1) << fixed << a << endl;

Re: try *_heap (+)

BTW(1), there is no need for "unsigned" since input is less than 2^31-1

There was an example of possible input in early posts on the forum:

[(2^31 - 1) + (2^31 - 1)] / 2 = 2^31 - 1

but

((2^31) - 1) + ((2^31) - 1) = 4 294 967 294

so if you don't know how to manage such a thing you should use unsigned int.

BTW there is no differences in allocated memory between "unsigned" and "signed int" but "unsigned" work faster.

Re: try *_heap (+)

one way to avoid overflow of calculating ((2^31) - 1) + ((2^31) - 1) is to compute

((2^31-1) * 0.5) + ((2^31-1) * 0.5) instead of ( ((2^31) - 1) + ((2^31) - 1) ) * 0.5

Re: use priority_queue <unsigned int>!!!!

thank you very much!

Re: use priority_queue <unsigned int>!!!!

Posted by

Pegasus 23 Mar 2013 14:22

I have learnt a lot ,thanks.

Re: use priority_queue <unsigned int>!!!!

I use G++ 4.9 and get MLE. Then I try G++ 4.9 C++ 11 and AC.

Why? :(