پاسخ سوال چارپک کوئرا

پاسخ سوال چارپک کوئرا

در این نوشته تمرین “چیهمونی؟” که در وب‌سایت کوئرا موجود است را برای شما کاربران عزیز حل کرده‌ایم.

پاسخ سوال چارپک کوئرا

دانشگاه تهران یکی از بهترین سلف‌های دنیا را دارد و کیفیت غذای آن فوق‌العاده است! میکائیل مسئول سلف دانشگاه تهران است و بسیار انسان منظمی است. هم‌چنین او به عدد چهار علاقه‌ی زیادی دارد (این علاقه ریشه در اعتقاد شدید او به علم ژنتیک دارد). به همین جهت، سیستم پخش غذا در دانشگاه تهران به این صورت است که غذاها به صورت چهار تا چهار تا بسته‌بندی می‌شوند. سپس در هر نوبت، یک گروه حداکثر چهار نفره داخل صف می‌شوند و میکائیل یکی از بسته‌ها را باز می‌کند. سپس به هر کدام از افراد داخل صف دقیقا یک غذا می‌دهد و برای حفظ عدالت بقیه‌ی غذاهای آن بسته را خودش می‌خورد. از آن‌جایی که در دانشگاه تهران میزان فشار بر روی دانشجوهای مختلف خیلی متفاوت است، بعضی از افراد یک غذا، بعضی دیگر دو غذا،‌ و حتی بعضی‌ها به علت فشار بسیار زیاد سه غذا می‌خواهند. تعداد غذاهایی که نفر $i$ ام می‌خواهد را a_i​ می‌نامیم. دانشگاه تهران مسئولین بسیار مهربانی دارد و به هر کس هر تعداد غذا که بخواهد، داده می‌شود ولی خب بودجه‌ی آن‌ها محدود است و می‌خواهند تا جایی که می‌توانند در تهیه‌ی غذاها صرفه‌جویی بکنند. حال آن‌ها از شما کمک خواسته‌اند و می‌خواهند بدانند که میکائیل حداقل چند بسته غذا باید تهیه کند. به آن‌ها کمک کنید تا ورشکست نشوند!!!

ورودی سوال چارپک

در سطر اول ورودی عدد n آمده است. در سطر دوم $n$ عدد آمده است که عدد i ام a_i​ است.

$$1\le n\le 5000$$

1 ≤ ai​ ≤ 3

خروجی سوال چارپک

در تنها سطر خروجی کم‌ترین تعداد بسته‌ی غذا که میکائیل باید تهیه کند را چاپ کنید.

حل سوال چارپک

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{
    int n, m, a[4] = {0}, saf;
    cin >> n;
    priority_queue<int> pq;
    for(int i=0; i<n; i++) {
        cin >> m;
        pq.push(m);
    }
    int t = 0;
    while(!pq.empty())
    {
        saf = min((int)pq.size(), 4);
        for(int i=0; i<saf; i++)
            a[i] = pq.top()-1, pq.pop();
        for(int i=0; i<saf; i++)
            if(a[i] > 0)
                pq.push(a[i]);
        t++;
    }
    
    cout << t << endl;
    return 0;
}

منبع سوال‌: وبسایت کوئرا

اگر روش حل بهتری برای “تمرین چارپک” دارید برای ما ارسال کنید تا با نام خودتان به اشتراک بگذاریم. اگر سوال خاصی را مدنظر دارید در بخش نظرات برای ما ارسال کنید تا حل آن سوال را در الویت محتوای سایت بگذاریم.