SRM div1 Easy MysticAndCandies

メモ

できなかった...

C-sum(low[i])がどの箱に入ってるかわからない。

最悪なケースは選ばない箱にどこに入ってるかわからない飴ができるだけ入っている状態。

良い選択方法としては

・lowが大きい順に選ぶ->選ぶ箱に最低限入っている飴を多くしたい

or

・highが小さいものを選ばない(highが大きい順に選ぶ)->選ばない箱に入る飴をできるだけ少なくしたい

の二つが考えられるので両方試して良い方を選択する。

コード

typedef long long ll;
typedef pair<ll, ll> P;
class MysticAndCandies {
public:
  int minBoxes(int C, int X, vector <int> low, vector <int> high) {
    int n = low.size();
    vector<P> v(n);
    FOR(i,0,n) v[i] = P(low[i], high[i]);
    sort(v.begin(), v.end());
    FOR(i,0,n) {
      C -= low[i];
    }

    // lowの大きい順に選んでいく->取れる飴の最大化を目指す？
    // lowの小さい順にあまりの雨がある
    int C2 = C;
    FOR(i,0,n) {
      int diff = v[i].second - v[i].first;
      v[i].first += min(diff, C2);
      C2 -= min(diff, C2);
    }
    ll sum = 0;
    int i = n - 1;
    int ret = 0;
    while(sum < X) {
      ret++;
      sum += v[i].first;
      i--;
    }
    
    // highの大きい順に選んでいく->選ばない箱に入るあめの最小化を目指す？
    // highの小さい順にあまりの雨がある
    FOR(i,0,n) v[i] = P(high[i], low[i]);
    sort(v.begin(), v.end());
    C2 = C;
    FOR(i,0,n) {
      int diff = v[i].first - v[i].second;
      v[i].second += min(diff, C2);
      C2 -= min(diff, C2);
    }
    sum = 0;
    i = n - 1;
    int ret2 = 0;
    while(sum < X) {
      ret2++;
      sum += v[i].second;
      i--;
    }
    return min(ret, ret2);
  }
};

lowが大きい順に選ぶ方法しか思いつかなかった。