結果
問題 | No.545 ママの大事な二人の子供 |
ユーザー |
![]() |
提出日時 | 2025-03-20 21:05:58 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 125 ms / 2,000 ms |
コード長 | 1,015 bytes |
コンパイル時間 | 252 ms |
コンパイル使用メモリ | 82,412 KB |
実行使用メモリ | 108,100 KB |
最終ジャッジ日時 | 2025-03-20 21:06:07 |
合計ジャッジ時間 | 3,299 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
import bisect n = int(input()) items = [] for _ in range(n): a, b = map(int, input().split()) items.append((a, b)) # 分割物品为前半和后半 m = n // 2 first_part = items[:m] second_part = items[m:] def get_diffs(items_part): diffs = {0} for a, b in items_part: new_diffs = set() for d in diffs: new_diffs.add(d + a) new_diffs.add(d - b) diffs = new_diffs return diffs s1 = get_diffs(first_part) s2 = get_diffs(second_part) s2_sorted = sorted(s2) min_abs = float('inf') for d1 in s1: target = -d1 pos = bisect.bisect_left(s2_sorted, target) # 检查pos和pos-1的位置 if pos < len(s2_sorted): candidate = s2_sorted[pos] current_abs = abs(d1 + candidate) if current_abs < min_abs: min_abs = current_abs if pos > 0: candidate = s2_sorted[pos-1] current_abs = abs(d1 + candidate) if current_abs < min_abs: min_abs = current_abs print(min_abs)