概要

全チームの募金総額の半分以上を集めるために、必要なチーム数の最小値を求める問題です。
できるだけ少ないチームで目標金額に到達したいので、募金額が大きいチームから順に選ぶのが最適です。

考察

全チームの募金総額を \(T\) とすると、選んだチームの合計金額が

\( \lceil T / 2 \rceil \)

以上になれば条件を満たします。

ここで重要なのは、チーム数を最小にしたいなら、募金額が大きいチームから選ぶのが最も効率的ということです。

例えば、募金額が

\(4, 3, 2, 1\)

だったとします。総額は \(10\) 円なので、目標は \(5\) 円です。

• 大きい順に選ぶと、\(4 + 3 = 7\) で \(2\) チーム
• 小さい順に選ぶと、\(1 + 2 + 3 = 6\) で \(3\) チーム

このように、大きい金額のチームを優先して選ぶことで、必要なチーム数を少なくできます。

また、あるチーム数 \(k\) で集められる最大金額は、募金額が大きい順に \(k\) 個選んだときです。
したがって、大きい順に \(k\) 個選んでも目標に届かないなら、他のどんな \(k\) 個を選んでも目標には届きません。

素朴にすべてのチームの選び方を試すと、選び方は \(2^N\) 通りあります。
制約では \(N \leq 10^6\) なので、この方法は到底間に合いません。

そこで、募金額を大きい順にソートし、先頭から順に足していくことで最小のチーム数を求めます。

アルゴリズム

1. \(N\) と配列 \(A\) を入力する。
2. 全チームの募金総額 \(T\) を計算する。
3. 目標金額を \(target = \lceil T / 2 \rceil\) とする。
   • 整数で計算する場合は、\(target = (T + 1) / 2\) と書けます。
4. 配列 \(A\) を降順にソートする。
5. 大きい金額から順に足していく。
6. 合計が \(target\) 以上になった時点のチーム数を出力する。

例えば、\(A = [2, 10, 3, 5]\) の場合を考えます。

総額は

\(2 + 10 + 3 + 5 = 20\)

なので、目標金額は

\(20 / 2 = 10\)

です。

降順に並べると

\(10, 5, 3, 2\)

となります。

先頭から足すと、最初の \(10\) だけで目標に到達するので、答えは \(1\) です。

計算量

• 時間計算量: \(O(N \log N)\)
  • 配列をソートする部分が最も重いです。
• 空間計算量: \(O(N)\)
  • 募金額を配列に保存するためです。

実装のポイント

募金額 \(A_i\) は最大で \(10^9\)、チーム数 \(N\) は最大で \(10^6\) です。
そのため、総額は最大で

\(10^9 \times 10^6 = 10^{15}\)

になります。

これは int には収まらないため、総額や累積和は long long 型で管理する必要があります。

また、半分以上を表す目標金額は

long long target = (total + 1) / 2;

と計算できます。

これは、\(total\) が奇数の場合にも正しく切り上げを行うためです。

ソースコード

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

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

    int N;
    cin >> N;

    vector<long long> A(N);
    long long total = 0;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        total += A[i];
    }

    sort(A.begin(), A.end(), greater<long long>());

    long long target = (total + 1) / 2;
    long long sum = 0;

    for (int i = 0; i < N; i++) {
        sum += A[i];
        if (sum >= target) {
            cout << i + 1 << '\n';
            return 0;
        }
    }

    return 0;
}

---

この解説は gpt-5.5-high によって生成されました。