概要

\(N\) 個のチームから募金額の合計が全体の半分以上（\(\lceil T/2 \rceil\) 以上）になるように選ぶとき、選ぶチーム数の最小値を求める問題です。

考察

まず、「合計を半分以上にしつつ、できるだけ少ないチーム数で達成する」ためにはどうすればよいかを考えます。

ここで重要な観察は、同じチーム数を選ぶなら、募金額の大きいチームから選ぶのが最も合計を大きくできるという点です。たとえば \(k\) 個のチームを選ぶとき、上位 \(k\) チームを選べばその \(k\) 個での合計は最大になります。

したがって、募金額を降順にソートして大きい方から順に足していき、累積和が初めて \(\lceil T/2 \rceil\) 以上になった時点で、そのチーム数が答えになります。

素朴に「すべての選び方を試す」と組合せの数が膨大（\(2^N\) 通り）になり、\(N\) が大きいと到底間に合いませんが、上記の貪欲な考え方により \(1\) 回ソートして順に足すだけで答えが求まります。

具体例で確認しましょう。たとえば \(A = [1, 3, 4, 2]\) のとき、総額は \(T = 10\) なので半分は \(\lceil 10/2 \rceil = 5\) です。降順に並べると \([4, 3, 2, 1]\) となり、

• \(4\)（\(1\) チーム）→ まだ \(5\) 未満
• \(4 + 3 = 7\)（\(2\) チーム）→ \(5\) 以上に到達

よって答えは \(2\) です。

アルゴリズム

1. 全チームの募金額の総和 \(T\) を求める。
2. 必要な金額の下限 \(\text{half} = \lceil T/2 \rceil\) を計算する。整数演算では \(\lceil T/2 \rceil = (T+1)/2\) として求められる。
3. 募金額を降順にソートする。
4. 大きい方から順に足し合わせ、累積和が \(\text{half}\) 以上になった時点で選んだチーム数を出力する。

これは「大きいものから貪欲に選ぶ」という典型的な貪欲法（greedy）です。

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的）
• 空間計算量: \(O(N)\)（募金額の配列を保持）

実装のポイント

• 総和や累積和のオーバーフローに注意します。\(A_i \leq 10^9\) かつ \(N \leq 10^6\) なので、総和は最大で約 \(10^{15}\) に達します。これは \(32\) ビット整数（int）の範囲を超えるため、long long 型を用いる必要があります。

• \(\lceil T/2 \rceil\) は、(T + 1) / 2 と書くことで整数のまま正しく天井除算が計算できます。\(T\) が偶数なら \(T/2\)、奇数なら \((T+1)/2\) となり、いずれも正しい結果になります。

• \(N\) が最大 \(10^6\) と大きいので、入力の読み込みは高速な方法（scanf など）を使うとよいでしょう。

  ソースコード

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

int main(){
    int N;
    scanf("%d", &N);
    vector<long long> A(N);
    long long T = 0;
    for(int i=0;i<N;i++){
        scanf("%lld", &A[i]);
        T += A[i];
    }
    sort(A.rbegin(), A.rend());
    long long half = (T + 1) / 2;
    long long sum = 0;
    int cnt = 0;
    for(int i=0;i<N;i++){
        sum += A[i];
        cnt++;
        if(sum >= half) break;
    }
    printf("%d\n", cnt);
    return 0;
}

この解説は claude4.8opus-high によって生成されました。