Twins

Twins

Codeforces easy

Given an array \(A\) of \(N\) integers, determine the minimum number of elements to select from \(A\) such that the sum of the selected elements is strictly greater than the sum of the remaining elements.

Solution

First, compute the sum of the array, which we’ll call total_sum.

Since we want to select the minimum number of elements, we want to take the largest elements first. To do this, we sort the array in increasing order and iterate over it in reverse (from n - 1 to 0) maintaining two values.

• selected_sum — the sum of elements we have chosen so far
  
• cnt — the count of elements selected

In each step, we check if selected_sum > total_sum - selected_sum. if the condition is true, we print cnt and terminate the program.

#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;
        }
    }
}