だからお前はだめなんだ。
はい。なんかとても悲しい気分のNafmoです。
priority_queueを使うとても素晴らしい問題に出会った気がした。
戦うほどのことはしていないが、とりあえず。
D: 3N Numbers - AtCoder Beginner Contest 062
本番でときたかった難易度な気がしてならない
完全に考察と発想で勝てる...と思ってる
問題概要
- 3Nの長さの数列が投げられる。
- 前からN個後ろからN個取る
ここで、クロスして取ることはできない(1 3&2 4など) - 前の総和-後ろの総和 を最大にして
ソートして幸せになりたい！！！！(TLEです)
毎回ソートするという考えしか浮かばず死亡。
解法
- 境目を決める。前と後でとる境目をN<=k<=2Nでスライドして
すべてのkに於いてもとめる - で、前の和はなるべく大きく。後ろの和は小さくしていく。
- 前N個の和をpriority_queue(大きい方が先に出る)にぶっこむ
その和を変数に保持しておく - 次の値をpushする。和を更新する(足す)
- キューの中で一番小さいものを抜く。和を更新する(引く)
- 後ろについても同じことをする。
- 後ろからN個の和をキュー(小さいほうが先に出る)にぶっこむ。同じく和を保持
- 4をやる
- 5と同じように、popして、一番大きいものを抜く
- 対応しているところの和で大きいものを出す。
注意事項。
int → long long int に気をつけて
INFの大きさ気をつけないと死ぬ
おわり。
