Решение задачи Близнецы с Codeforces

Без пояснения   Просмотров: 27


Представьте себе, что у Вас есть брат или сестра-близнец. Это кажется очень необычным, что в мире есть еще один человек, который выглядит также как Вы. И даже трудно сказать хорошо это или плохо, что Вы как будто не один такой на этой планете. А если у Вас и вправду есть близнец, тогда Вы точно знаете, каково это.

Теперь представьте себе обычное утро в Вашей семье. Пока вы еще спите, мама уже собирается на работу. Она так торопилась, что чуть не забыла оставить вам, ее любимым детям, немного денег, чтобы покушать в школе в столовой. В кошельке она нашла некоторое количество монет, а именно n монет произвольных достоинств a1, a2, ..., an. Времени у нее было мало, поэтому поделить монеты она не успела. Тогда она написала записку, в которой попросила вас разделить деньги поровну.

Проснувшись, Вы нашли оставленные мамой монеты и прочитали записку. «Но зачем делить монеты поровну?» — подумали Вы, ведь Ваш близнец еще спит и ничего не узнает. Поэтому Вы решили поступить следующим образом: выбрать себе некоторое подмножество монет, так чтобы сумма достоинств взятых Вами монет оказалась строго больше, чем сумма достоинств оставшейся части монет, которая достанется Вашему близнецу. Однако, Вы справедливо решили, что если взять слишком много монет, то Ваш близнец подумает, что Вы его обманули. Поэтому, чтобы не вызывать подозрений, Вы решили взять наименьшее количество монет, сумма достоинств которых окажется строго больше суммы достоинств оставшихся. Исходя из этого, выясните, какое минимальное количество монет Вам понадобится взять, чтобы разделить их описанным образом.

Код

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, s = 0;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        s+=a[i];
    }
    int c = 0;
    sort(a.begin(), a.end());
    for(int i = a.size() - 1; i >= 0; --i){
        c+=a[i];
        if(c > s - c){
            cout << a.size() - i;
            return 0;
        }
    }
    return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться