الشاورميادا

الشاورميادا

الأولمبياد الوطني للبرمجة 2026 - المسابقة الرابعة، اليوم الأول

الزمن المحدد: 1 ثانية الذاكرة المحددة: 256 ميجابايت

إلى جانب المسابقة الوطنية للمعلوماتية، تستضيف الرياض أيضًا شاورميادا هذا العام. قرر سلطان أن يفوز هذا العام وأن يحصل على كمية كبيرة من الجوائز اللذيذة.

الشاورميادا هي مسابقة يحضر فيها كل مشارك \(N\) شاورما ويقيس أوزانها بطريقة محددة:

• يقيس سلطان أولًا الوزن الكلي لجميع الشاورما دفعة واحدة، ويكتب النتيجة على اللوح.
• بعد ذلك، يقسم الشاورما التي تم قياسها إلى مجموعتين غير فارغتين ومنفصلتين، ثم يقيسهما.
• إذا كانت المجموعة المقاسة تحتوي على شاورما واحدة فقط، فلا يتم تقسيمها أكثر؛ بل تُوضع جانبًا وتنتهي عمليتها.
• مجموع جميع الأعداد المكتوبة على اللوح يمثل نتيجة سلطان النهائية في المسابقة.

يريد سلطان أن يعرف كيف يجري التقسيمات بعد كل قياس بحيث تكون نتيجته أكبر ما يمكن. وبما أنه مشغول جدًا، فقد طلب مساعدتك، وفي المقابل سيوصلك إلى بعض من أفضل الشاورما في الرياض.

المدخلات

يحتوي السطر الأول على عدد طبيعي \(T\)، حيث \(1 \le T \le 10\)، وهو عدد حالات الاختبار.

تُعطى كل حالة اختبار بالصيغة التالية:

• يحتوي السطر الأول على عدد طبيعي \(N\)، حيث \(1 \le N \le 10^5\)، وهو عدد الشاورما التي يحضرها سلطان.

• يحتوي السطر الثاني على \(N\) عددًا طبيعيًا \(A_1, A_2, \dots, A_N\)، حيث يمثل \(A_i\) وزن الشاورما رقم \(i\) بالغرام، و\(1 \le A_i \le 10^9\) لكل \(1 \le i \le N\).

المخرجات

لكل حالة اختبار، اطبع عددًا طبيعيًا واحدًا: أكبر نتيجة يمكن أن يحققها سلطان في تلك الحالة.

التقييم

المهمة الفرعية	قيود إضافية	النقاط
\(1\)	\(T = 1\), \(N \le 20\)	\(12\)
\(2\)	\(N \le 1000\)	\(19\)
\(3\)	\(A_1 = A_2 = \ldots = A_N\)	\(25\)
\(5\)	لا توجد قيود إضافية	\(44\)

أمثلة

المدخلات

1
3
20 20 20

المخرجات

160

المدخلات

1
3
12 7 18

المخرجات

104

الملاحظات

ملاحظة: العملية تكرارية: بعد قياس مجموعة، يكرر سلطان الإجراء نفسه على تلك المجموعة إذا كانت تحتوي على أكثر من شاورما واحدة. لا تنتهي العملية إلا عندما تحتوي كل مجموعة على شاورما واحدة بالضبط.

الشرح: يقيس سلطان أولًا الوزن الكلي \(20 + 20 + 20 = 60\)، ثم يقسم الشاورما إلى مجموعتين.

تحتوي المجموعة الأولى على شاورمتين وزنهما \(20\) و\(20\)، وتحتوي المجموعة الثانية على شاورما واحدة وزنها \(20\).

بعد ذلك يقيس المجموعة الأولى: \(20 + 20 = 40\).

ثم يقسمها إلى مجموعتين، تحتوي كل منهما على شاورما واحدة وزنها \(20\). وبعد قياس المجموعة الثانية، يكتب \(20\) على اللوح، وتُوضع تلك الشاورما جانبًا. ويحدث الأمر نفسه للمجموعتين الثالثة والرابعة.

تصبح الأعداد الموجودة على اللوح \(60,\ 40,\ 20,\ 20,\ 20\)، ومجموعها هو \(160\).

الحل

فكّر في العملية بالعكس. في البداية كل شاورما مجموعة مستقلة. دمج مجموعتين وزناهما \(x\) و\(y\) ينشئ المجموعة الأم ويضيف \(x+y\) إلى النتيجة. لتعظيم المجموع، ادمج في كل مرة أثقل مجموعتين كي تدخل أوزانهما في أكبر عدد من القياسات اللاحقة، واستخدم طابور أولوية أعظميًا. تُقاس حبات الشاورما منفردة أيضًا، فابدأ الإجابة بمجموع أوزانها. التعقيد \(O(N\log N)\) لكل حالة.

#include <iostream>
#include <queue>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tests;
    cin >> tests;

    while (tests--) {
        int n;
        cin >> n;

        priority_queue<long long> groups;
        long long answer = 0;

        for (int i = 0; i < n; i++) {
            long long weight;
            cin >> weight;
            groups.push(weight);
            answer += weight;
        }

        while (groups.size() > 1) {
            long long first = groups.top();
            groups.pop();
            long long second = groups.top();
            groups.pop();

            long long combined = first + second;
            answer += combined;
            groups.push(combined);
        }

        cout << answer << '\n';
    }
}