آخرین لطیفه‌گویی شنونده‌افکن
خوش‌بختانه موقع شام، ی.ا.د.ا.ک و دوستانش به‌قدری برای قاضی جُک گفتند که قاضی یادش رفت میزان بدیُمنی میزها را حساب کند و فقط از خنده روی زمین می‌غلطید!
فردای آن‌روز به اصرار آقای کاف، تصمیم گرفته‌شد که دانش‌پژوهان به باشگاه برگردند امّا به‌دلیل لذّتی که قاضی در مهمانی «مرغ افکن» از جُک‌های دانش‌پژوهان برده بود، از آن‌ها خواست که قبل از رفتن از «شیرافکن» همه‌ی دانش‌پژوهان همه‌ی جک‌هایی که بلد هستند را یک به یک برای او تعریف کنند!
ی.ا.د.ا.ک این‌بار واقعاً نگران شد. از طرفی او می‌دانست که اگر کسی جُکی بداند ولی به قاضی نگوید، ممکن است بعداً گندش در بیاید و قاضی این‌بار واقعاً فرمان قتل همه را صادر کند! از سوی دیگر، ی.ا.د.ا.ک می‌دانست که جُک گفتن بعضی از دانش‌پژوهان واقعاً بی‌مزه است و ممکن است باعث شود قاضی از کوره در برود!
ی.ا.د.ا.ک با یک پرس‌وجوی ساده فهمید که دانش‌پژوه $i$اُم، $j_i$ تا جُک بلد است و مجموع میزان بامزگی جُک‌های او نیز $w_i$ است. هم‌چنین ی.ا.د.ا.ک به‌خاطر آورد که اگر قاضی در انتهای شنیدن تمام جُک‌های یک نفر احساس کند که میانگین بامزگی جُک‌هایی که تا آن لحظه شنیده از یک مقدار خاصّی کم‌تر است، فکر می‌کند که دانش‌پژوهان قصد کم‌کاری دارند و در نتیجه فرمان قتل همه را صادر می‌کند!
با این وصف، الگوریتمی از زمان اجرای $O(n\log n)$ ارائه دهید که با داشتن $j_i$ و $w_i$ ها، ترتیبی برای جُک گفتن دانش‌پژوهان ارائه دهد که شانس زنده‌ماندن دانش‌پژوهان بیشینه شود. به بیان دقیق‌تر، اگر افراد طبق آن ترتیب جُک بگویند، حداقل میانگین بامزگی جک‌های گفته‌شده تا پایان جُک گفتن هر یک از افراد باید بیشینه شود. الگوریتم خود را تحلیل و اثبات کنید.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
