ABC127 D Integer Cards
総和を大きくしたい状況なので,
$ A_i
は小さい方から, 書かれている整数の大きい方から操作していくのが最適だということがわかる. しかしカードはとてもたくさんあるので, すべてのカードを通常の配列でもって扱うことは不可能である. ここで貪欲に考えると, 大きい方から
$ N
個取っておくことで最適にすることができることがわかる. よってこの問題を貪欲法を用いて,
$ O(N log N)
で解くことができた.
実装例:
https://atcoder.jp/contests/abc127/submissions/19916261