SRM536 Div1 Medium

500

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

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

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

view plainprint?

1. class RollingDiceDivOne {  
2. public:  
3.   long long mostLikely(vector <int> D_)  
4.   {  
5.     vector<lli> D(D_.begin(), D_.end());  
6.     if (D.size() == 1) return 1;  
7.   
8.     const int N = D.size();  
9.     sort(D.begin(), D.end());  
10.   
11.     for (int i = 0; i < N; ++i) {  
12.       --D[i];  
13.     }  
14.   
15.     lli a = accumulate(D.begin(), D.end(), 0LL) - D.back();  
16.     lli b = accumulate(D.begin(), D.end(), 0LL) / 2;  
17.   
18.     return N + min(a, b);  
19.   }  

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);
  }