この問題を解いています。
https://www.codingame.com/ide/puzzle/simple-load-balancing
n台のサーバがあって、追加で作業がtask個入ってくる。n台のサーバには
すでにスペース区切りの数値の作業が入っている。全サーバ間の負荷の差
が最小になるようにtaskを振り分けた時、その最大と最小の差はいくつ？
問題の数の例
100台のサーバに10000の追加タスク、各サーバーの現在のタスクは...
59835,83610.3161....と入っています
まず思いついたのはサーバーをソートして小さい方から1ずつ足していき
隣の大きい数を越えそうならなんとかするみたいなもの。ただ一番やっか
いな問題だとtaskが100000000なのでおそらく時間切れ。
次に思いついたのはソートして小さい順に並べ、隣との差が残りtask未満
ならごっそり足すというもの。2，2，2，5，100とか並んで残りタスクが10なら
5，5，5，5，100 残り1とかにしなければならない。残り１は先頭に足す。
まあこれなら少しややこしいけどなんとかなりそう。さらに問題になりそうな
のは先頭から揃えていく方法だと、あふれた時の対処。プログラムを作りな
がら、あふれたら均等割で割り切れれば差は0割り切れない時は必ず1と
気がついたのでそのロジックを然るべき場所に追加、したものが下の解答
ちなみに解答を解くと同じ言語で解いた他の方のプログラムも見ることが
できます。他の方はだいたい20行未満で解いています。まだまだの解き方
のようです。
基本的なロジックは変えないで、最後にサーバーの状態を作る無駄な演算
を削って、いくつかの処理をまとめて、3項演算子で改行を減らして、変数を
減らしたり名前を変えたりしてみたものがこちらです。
削りすぎたので、あとで見てもわからなくなります。
