SRM560 Div1 Easy

250

貪欲。

class TomekPhone {
public:
  int minKeystrokes(vector <int> os, vector <int> ks)
  {
    const int N = ks.size();

    vector<int> v[N];
    sort(os.begin(), os.end());
    reverse(os.begin(), os.end());

    const int inf = 1 << 29;
    for (int i = 0; i < os.size(); ++i) {
      int idx = 0;
      int mn = inf;
      for (int j = 0; j < N; ++j) {
        if (v[j].size() < ks[j]) {
          if (mn > v[j].size()) {
            mn = v[j].size();
            idx = j;
          }
        }
      }
      if (mn == inf) break;
      v[idx].push_back(os[i]);
    }

    int cnt = 0;
    for (int i = 0; i < N; ++i) {
      cnt += v[i].size();
    }
    if (cnt != os.size()) return -1;

    int sum = 0;
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < v[i].size(); ++j) {
        sum += (j + 1) * v[i][j];
      }
    }

    return sum;
  }
};