keidaroo’s diary

底辺系競プロer

SRM608 div1 easy MysticAndCandies

概要

n個の箱にキャンディが合計でC個入っている

また、各箱にはlow[i]~high[i]個キャンディが入っている

今X個最低でとりたい。必ずX個以上取れるような箱の選び方の最小値(箱を何個選ぶか)はなんでしょう??!

解法

まずこれは貪欲だが、一つの貪欲ではなくて2つの貪欲が存在する

1. 選んだ箱のlowの総数がX以上
2. max(0,C - (すべての箱のhighのSum - 選んだ箱のi個目までのhighのSum))>=X

のうちどちらかである。

両方同時に成り立つことはあり得なくて、なぜかというと

1と2以外のときは自分の選んでいない箱が中途半端にキャンディが入っているときであって、それはむしろ自分にとって甘えなので「すべての場合において成り立つ」とはとうてい言えないからだ。

余談ですが

これDPでもできませんか?

DP[何個選択しないか][何個目についてみているか]

というようにし、再帰DPの外に選択していないやつのmaxの総和、選択した奴のminの総和ってやればできそうかな、とは思いましたが萎えたので残念ながら実装していません。すみません。

コード

#include <bits/stdc++.h>
#define REP(i, n) for (signed long long i = 0; i < (n); i++)
using namespace std;

class MysticAndCandies {
public:
  int minBoxes(int C, int X, vector<int> low, vector<int> high) {
    int highsum = accumulate(high.begin(), high.end(), 0);

    int himos = 0, limos = 0;
    sort(high.begin(), high.end(), greater<int>());
    sort(low.begin(), low.end(), greater<int>());
    REP(i, low.size()) {
      himos += high[i], limos += low[i];

      if (limos >= X || C - highsum + himos >= X)
        return i + 1;
    }
  }
};