SRM536 Div1 Medium

500

http://community.topcoder.com/stat?c=problem_statement&pm=11797&rd=14728

(総和の半分) or (総和 - 最大値)

(総和の半分)はすぐに思いつく。
(総和 - 最大値)は分からなかったので小さいケースをいくつか手で試した。

class RollingDiceDivOne {
public:
  long long mostLikely(vector <int> D_)
  {
    vector<lli> D(D_.begin(), D_.end());
    if (D.size() == 1) return 1;

    const int N = D.size();
    sort(D.begin(), D.end());

    for (int i = 0; i < N; ++i) {
      --D[i];
    }

    lli a = accumulate(D.begin(), D.end(), 0LL) - D.back();
    lli b = accumulate(D.begin(), D.end(), 0LL) / 2;

    return N + min(a, b);
  }