SRM657 div1 easy ProblemSets

考えたこと

• EMでEとして使う問題数をw、Mとして使う問題数をx、MHでMとして使う問題をy、Hとして使う問題数をzとする
• min(E+w, M+x+y, H+z)を最大化すればよい
• 最小の最大化はにぶたんをしたくなる
• 問題セットの数cntを作れるかの判定をしたい
• Eがcntより小さければEMからその分Eに使うしかない、Hについても同様
• EとHに使わないといけない問題を使ったあとMに使える問題数がcnt以上ならcnt個はつくれる
• O(1)で判定ができるので二分探索ができた

二分探索がすんなり思いついてよかった

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

class ProblemSets {
   public:
   long long maxSets(long long E, long long EM, long long M, long long MH, long long H)
  {
    ll lb = 0, ub = 2e18;

    auto check = [&](ll mid) -> bool {
      ll a = E, b = EM, c = M, d = MH, e = H;
      if(a < mid) {
        if(b < mid-a) return false;
        b -= mid - a;
        a = mid;
      }
      if(e < mid) {
        if(d < mid-e) return false;
        d -= mid-e;
        e = mid;
      }
      return b+c+d >= mid;
    };

    while(ub-lb > 1) {
      ll mid = (lb+ub)/2;
      // cout << lb << " " << mid << " " << ub << endl;
      if(check(mid)) {
        lb = mid;
      } else {
        ub = mid;
      }
    }

    return lb;
  }
};