پیدا کردن مین و ماکس

[Azar.099]

سلام
من سه تا فانکشن دارم add min max . درهر بار یک عدد با add به اعدادم اضافه میشه . و با هر بار انتخاب فانکشن min باید مینیمم از این اعداد را پیدا کنم در o(1) و اونو حذف کنم و با هر بار انتخاب فانکشن max باید ماکسیمم این اعداد در o(1) پیدا کنم و حذف کنم .
الان مشکل من با الگوریتمشه . هرجوری میرم نمیشه در o(1) همچین کاری کرد
خودم گفتم که سه تا استک بگیرم یکی کل اعداد یکی اعداد ماکس یکی اعداد مین ... اما ذخیره مین و ماکس ها خودش دوباره مشکل میشه
ممنون میشم راهنماییم کنید

[pbm_soy]

بیشتر توضیح میدادی!
هدفت چیه ؟ و دقیقا میخوای چیکار کنی؟ منظورت از O(1) چیه؟
اعداد کجا هستند؟
add یک عدد تصادفی به اعدادت اضافه میکنه؟

[Azar.099]

نه add(input) از کاربر ورودی میگیره
یعنی کاربر یا میتونه مین را انتخاب کنه یا ماکس و یا همین تابع بالا را
O(1) یعنی اینکه اگر کاربر مین یا ماکس را انتخاب کرد بدون هیچ هزینه ای بتونه اونها را پیدا کنه و بعد باید اون را حذف کنه

[rahnema1]

سلام
خب مشابه این سوال معمولا در درسهای مقدماتی برنامه نویسی مطرح می شه
میگن یه تعداد ورودی با مثلا cin بگیرید و بدون اینکه در آرایه ذخیره کنید max و min را در انتها نمایش بدید
کار پیچیده ای هم نیست
البته شما سوال را خیلی واضح مطرح نمی کنید

[Azar.099]

سلام
خب مشابه این سوال معمولا در درسهای مقدماتی برنامه نویسی مطرح می شه
میگن یه تعداد ورودی با مثلا cin بگیرید و بدون اینکه در آرایه ذخیره کنید max و min را در انتها نمایش بدید
کار پیچیده ای هم نیست
البته شما سوال را خیلی واضح مطرح نمی کنید
سلام
ببینید ما داریم یه بازی میکنیم که کاربر سه تا فانکشن داره . ادد مین ماکس ... با ادد عدد اضافه میکنه . با مین مینیمم اون اعداد را پیدا میکنه و حذف میکنه و ماکس ماکسمم اعداد را پیدا میکنه و حذف میکنه . این فانکشن ها فقط یه بار استفاده نمیشن . مثلا اول کاربر وارد میکنه میگه من میخوام 20 خط فانکشن وارد کنم . بعد میتونه توی این 20 خط 10 بار عدد وارد کنه و 10 بار از مین و ماکس استفاده کنه . هربار استفاده از مین و ماکس باید در o(1) پیدا و حذف بشن

[rahnema1]

یعنی چی 20 خط فانکشن وارد کنه؟
لطفا اون نمونه سوال که گفتم راه حلش را بگید تا خورده خورده بریم جلو

[Azar.099]

سلام
خب مشابه این سوال معمولا در درسهای مقدماتی برنامه نویسی مطرح می شه
میگن یه تعداد ورودی با مثلا cin بگیرید و بدون اینکه در آرایه ذخیره کنید max و min را در انتها نمایش بدید
کار پیچیده ای هم نیست
البته شما سوال را خیلی واضح مطرح نمی کنید

خب توی این سوال شما اولا که یکبار قراره مین و ماکس پیدا بشن و نمایش داده بشن ... دوما به داده ها بعد از یک بار پیدا کردن مین و ماکس داده اضافه نمیشه
سوما در این حالت با دو تا متغیر و دو تا ایف میتونیم مین و ماکس را بدست بیاریم .

[rahnema1]

خب شما که دارید جوابش را می گید. اگه بتونید کد را بذارید

[Azar.099]

خب شما که دارید جوابش را می گید. اگه بتونید کد را بذارید

خب من که دارم میگم این سوال با اینی که شما میگی فرق داره !!!

[rahnema1]

خب همون ها را می تونید توی یه چیزی شبیه استک بذارید

[Azar.099]

خب همون ها را می تونید توی یه چیزی شبیه استک بذارید
خب من دقیقا مشکلم با نوع ذخیره کردن توی استکه
به نظرتون نمیشه با هیپ رفت ؟ مین هیپ برای به دست اوردن مین و ماکس هیپ برای بدست اوردن ماکس
فقط مشکل اینکارم اینه که هیپیفای کردن اونها خودش پیچیدگیش زیاد تره ....
:((((

[rahnema1]

خب من دقیقا مشکلم با نوع ذخیره کردن توی استکه
:((((
از همون اول باید اشاره می کردید که در کدم قسمت اشکال دارید
شما از deque استفاده کنید که از دو طرف قابل حذف و اضافه هست

[Azar.099]

سلام
خودم گفتم که سه تا استک بگیرم یکی کل اعداد یکی اعداد ماکس یکی اعداد مین ... اما ذخیره مین و ماکس ها خودش دوباره مشکل میشه
ممنون میشم راهنماییم کنید


از همون اول باید اشاره می کردید که در کدم قسمت اشکال دارید
شما از deque استفاده کنید که از دو طرف قابل حذف و اضافه هست

اقای راهنما من که همون اول کلام گفتم ... !!!!!!!!!!
در ضمن سوالم با هیپ حل شد . ممنون .

[rahnema1]

اگه ممکنه جواب سوال را اینجا بذارید چون من تصمیم دارم جواب خودم را اینجا بذارم

[Azar.099]

فکر کنم هنوز یه جایی مشکل داره

#include "iostream"
#include <stdlib.h>


using namespace std;


int maxnum = 0;
int minnum = 0;
int outnum = 0;
int maxArr[200000];
int minArr[200000];
int out[200000];


void maxHeapify(long int n)
{
if (n < 1 || n > maxnum / 2)
return;


long int l = 2 * n;
long int r = 2 * n + 1;
long int bigC = n;


if (l <= maxnum && maxArr[l] > maxArr[bigC])
bigC = l;
if (r <= maxnum && maxArr[r] > maxArr[bigC])
bigC = r;


if (n != bigC)
{
long int c = maxArr[n];
maxArr[n] = maxArr[bigC];
maxArr[bigC] = c;


maxHeapify(bigC);
}


return;
}




void minHeapify(long int n)
{
if (n < 1 || n > minnum / 2)
return;


long int l = 2 * n;
long int r = 2 * n + 1;
long int little = n;


if (l <= minnum && minArr[l] < minArr[little])
little = l;
if (r <= minnum && minArr[r] < minArr[little])
little = r;


if (little != n)
{
long int c = minArr[n];
minArr[n] = minArr[little];
minArr[little] = c;


minHeapify(little);
}


return;
}


void add(long int i)
{
maxnum++;
minnum++;


maxArr[maxnum] = i;
minArr[minnum] = i;


int j = maxnum;
while (j > 1 && maxArr[j] > maxArr[j / 2])
{
long int c = maxArr[j];
maxArr[j] = maxArr[j / 2];
maxArr[j / 2] = c;


j /= 2;
}


j = minnum;
while (j > 1 && minArr[j] < minArr[j / 2])
{
long int c = minArr[j];
minArr[j] = minArr[j / 2];
minArr[j / 2] = c;


j /= 2;
}
}


int main()
{
long int np;
char c[10000] = { 0 };
cin >> np;


while (np-- > 0)
{
cin >> c;
if (c[0] == 'a')
{


long int i;
i = atoi(c+4);
add(i);


}
else if (maxnum == 0 || minnum == 0)
cout << "";
else if (c[1] == 'a') //max
{
cout << maxArr[1] << endl;
out[outnum] = maxArr[1];
outnum++;


maxArr[1] = maxArr[maxnum];
maxnum--;
maxHeapify(1);
}
else if (c[1] == 'i') //min
{
cout << minArr[1] << endl;
out[outnum] = minArr[1];
outnum++;


minArr[1] = minArr[minnum];
minnum--;
minHeapify(1);
}
}

[rahnema1]

همون روش heap که اشاره کردید کاملا درسته
ابتدا فکر می کردم با deque حل می شه که بعد متوجه شدم و اصلاح کردم
اینجا از priority_queue استفاده کردم که تقریبا همون heap هست


#include <queue>
#include <iostream>
#include <functional>

class Game
{
private:
std::priority_queue<int,std::vector<int>, std::less<int>> max_queue;
std::priority_queue<int,std::vector<int>, std::greater<int>> min_queue;
public:
void add(int num)
{
max_queue.push(num);
min_queue.push(num);
}
int get_min()
{
int min = min_queue.top();
min_queue.pop();
return min;
}
int get_max()
{
int max = max_queue.top();
max_queue.pop();
return max;
}
};
int main()
{
Game game;
game.add(10);
game.add(20);
std::cout<< game.get_max() << "\n";
game.add(4);
game.add(2);
std::cout<< game.get_min() << "\n";
std::cout<< game.get_min() << "\n";
std::cout<< game.get_min() << "\n";
game.add(13);
std::cout<< game.get_max() << "\n";
}

[Azar.099]

راه حلتون خیلی خوبه
ممنون .