ABC187 D - Choose Me

考えたこと

まずはじめにA+Bが大きい順に取っていけばいいんじゃないかと思って出したがWA
よく考えると

3
3 2
2 6
6 1

みたいな入力で死ぬ
この場合は2番目でなく、3番目を取ったほうが得になる
自分の利益だけではなく相手の利益をへらすことも考えなくてはいけない
問題を数式で書くと、

$$\sum_{i \in S} (A_i + B_i) - \sum_{i \in T} (A_i) > 0 \\ Sは高橋君が選んだ街の集合 \\ Tは高橋君が選ばなかった街の集合 \\ |S|を最小化$$

式変形すると

$$\sum_{i \in S} (2A_i + B_i) - \sum_{i \in T \cup S} (A_i) > 0$$

$\sum_{i \in T \cup S} (A_i)$は定数なので、
集合Sを決めるときは$2A_i + B_i$が大きい順にとっていけばいいとわかる

提出コード

https://atcoder.jp/contests/abc187/submissions/19144858
にぶたんで書いたけどはじめに条件みたすところでreturnすればいいだけだった