📑
ABC365 C Transportation Expensesを理解し忘れないようにする
本記事を書いた意図
ABC365Cが解けなかったので理解する。それだけだと忘れる+人に説明する代わりにzennでのアウトプットで理解度を深める
問題の概要
N人それぞれに交通費の補助が割り当てられるが、その合計がM円をギリギリ超えないように交通補助費の上限値を求める。
解き方
交通補助Xを0から限界値+1(10^9+1)から2分探索して問題文通りの計算を行い、⚪︎と×の境界値を見つける。
あとは境界値の⚪︎を出力すればいい。
2分探索を行っているから計算量はlog10^9、問題文通りの計算はN回、よって計算量は(Nlog(10^9))となる。
回答コード
参考元
ABC365Cの解説放送
Discussion