まず、各選挙区について「あと何人の青木派を鞍替えさせれば 議席を獲得できるか？」を計算します。これは \(X_i\) と \(Y_i\) の大小で場合分けを行うと、

• \(X_i \gt Y_i\) のとき：すでに高橋派が多数派なので、\(0\) 人
• \(X_i \lt Y_i\) のとき：高橋派が \(\frac{X_i + Y_i + 1}{2}\) 人以上にならないと多数派にならないので、\(\frac{X_i + Y_i + 1}{2} - X_i = \frac{Y_i - X_i + 1}{2}\) 人

になります。この人数を \(W_i\) とおきます。

また、\(S = \sum_{i=1}^n Z_i\) とします。\(S, W_i\) を使うとこの問題は次のように読み替えられます。

\(N\) 個の選挙区がある。
\(i\) 番目の選挙区では高橋君は \(W_i\) 人鞍替えさせると \(Z_i\) 議席を得られる。 高橋君が \(\frac{S+1}{2}\) 議席以上を獲得するには何人鞍替えさせればよいか？

この問題は ナップサック問題と同じ構造をしています。そのため ナップサック問題と同様に動的計画法で \(\mathrm{O}(NS)\) で解くことができます。具体的には、DP テーブル \(\mathrm{dp}\) を

• \(\mathrm{dp}[n]\) :ちょうど \(n\) 議席得られるのに必要な鞍替えする人の人数 (ちょうど \(n\) 議席得られることがありえない場合は \(\infty\))

と定義して動的計画法を行えばよいです。手続き的に説明すると次のようになります。

• \(\mathrm{dp}\) を長さ \(S+1\) の配列とする。はじめ \(\mathrm{dp}[0] = 0\) で、それ以外のマスは \(\infty\) で初期化されている。
• \(i=1, 2, \dots, N\) の順に次の操作を行う。
  • \(n=S, S-1, \dots, Z_i\) の順に次の操作を行う。
    • \(\mathrm{dp}[n]\) を \(\min(\mathrm{dp}[n], \mathrm{dp}[n-Z_i] + W_i)\) に更新する。
• 操作後の DP テーブルのうち \(\mathrm{dp}[(S+1)/2], \mathrm{dp}[(S+1)/2 + 1], \dots, \mathrm{dp}[S]\) に書かれている値の最小値が問題の答えとなる。

計算量は \(\mathrm{O}(N \sum_{i=1}^N S_i)\) で十分高速です。

• 実装例 (C++)

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

int main() {
  long long inf = 1e18;

  int N;
  cin >> N;
  vector<int> X(N), Y(N), Z(N);
  for (int i = 0; i < N; i++) cin >> X[i] >> Y[i] >> Z[i];

  int z_sum = accumulate(begin(Z), end(Z), 0);
  vector<long long> dp(z_sum + 1, inf);
  dp[0] = 0;
  for (int i = 0; i < N; i++) {
    int x = X[i], y = Y[i], z = Z[i];
    int w = max(0, (x + y) / 2 + 1 - x);
    for (int j = z_sum; j >= z; j--) {
      dp[j] = min(dp[j], dp[j - z] + w);
    }
  }

  long long ans = inf;
  for (int j = z_sum / 2 + 1; j <= z_sum; j++) ans = min(ans, dp[j]);
  cout << ans << endl;
}