Twins

Twins

Codeforces easy

لديك مصفوفة \(A\) تحتوي على \(N\) أعداد صحيحة، حدد أقل عدد من العناصر التي يجب اختيارها من \(A\) بحيث يكون مجموع العناصر المختارة أكبر من مجموعة العناصر المتبقية.

Solution

أولاً، احسب مجموع المصفوفة، والذي سنسميه total_sum.

بما أننا نريد اختيار الحد الأدنى من العناصر، نريد أخذ أكبر العناصر أولاً. للقيام بذلك، نقوم بترتيب المصفوفة بترتيب تصاعدي نقوم بالمرور عليها بشكل عكسي (من n - 1 إلى 0) مع الحفاظ على قيمتين:

• selected_sum — مجموع العناصر التي اخترناها حتى الآن
  
• cnt — عدد العناصر المختارة

في كل خطوة، نتحقق مما إذا كان selected_sum > total_sum - selected_sum. إذا تحقق الشرط، نطبع cnt ونتوقف عن البرنامج.

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

int main() {
    int n;
    cin >> n;

    int a[n];
    int total_sum = 0;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        total_sum += a[i];
    }

    sort(a, a + n);

    int selected_sum = 0;
    int cnt = 0;

    for (int i = n - 1; i >= 0; i--) {
        selected_sum += a[i];
        cnt++;

        if (selected_sum > total_sum - selected_sum) {
            cout << cnt << endl;
            break;
        }
    }
}