読者です 読者をやめる 読者になる 読者になる

UVa410 Station Balance

問題
https://uva.onlinejudge.org/external/4/410.html
Given C chambers which can store 0, 1 or 2 specimens, S specimens and a list M of the masses of the S specimens, determine which chamber should store each specimen in order to minimize imbalance. A = (\sum_{j=1}^S M_j) / C, Imbalance = \sum_{i=1}^C |X_i - A|


解法
Competitive Programming 3 P.89 〜

Greedyで解ける。

自明な観察として、2つ以上のmassが入っているchamberと空のchmaberがあれば、1つは空のchamberに移し替えた方が良いというものがある。

他に重要な観察として、chamberに1個ずつ割り振って、massが余る、つまりS > Cのとき、S - C個は、すでにmassが入っているchamberに入れなければならないことがある(鳩ノ巣原理)

重さ0のmassを0個以上追加して、S = 2Cが成り立つようにしよう。重さをソートすると、上の観察より、大きい重さをもつものと小さい重さを持つものとを順にペアにして詰めていけば良いことが分かる。Load Balancingの問題。

int main() {

  for(int C, S; cin >> C >> S;) {
    int sp[2*C], tot = 0; zero(sp);
    rep(i, S) cin >> sp[i], tot += sp[i];
    sort(sp, sp + 2*C);

    const double AM = 1.0 * tot / C;
    double ans = 0.0;

    static int tc = 1;
    cout << "Set #" << tc++ << endl;
    rep(i, C) {
      printf(" %d:", i);
      if(sp[i]) cout << " " << sp[i];
      if(sp[2 * C - i - 1]) cout << " " << sp[2 * C - i - 1];
      puts("");
      ans += abs(sp[i] + sp[2 * C - i - 1] - AM);
    }
    printf("IMBALANCE = %.5f\n\n", ans);
  }
  
  return 0;
}