CODE FESTIVAL 2015 予選B C - 旅館

問題について考えたこと

問題文へ

各予約の人数と各部屋の定員が共にであるため、予約毎に部屋があるか調べても間に合うと考えました。

一つの部屋に一つの予約、予約人数<=部屋の定員であることから、人数の多い予約から調べる事としました。

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


int main(void) {
  int N, M;
  cin >> N >> M;
  vector<int> A(N);
  rep(i, N) cin >> A[i];
  vector<int> B(M);
  rep(i, M) cin >> B[i];

  sort(A.rbegin(), A.rend());
  sort(B.rbegin(), B.rend());

  int a = 0;
  int b = 0;
  while (b < B.size()) {
    while (a < A.size()) {
      if (B[b] <= A[a]) {
        ++a;
        ++b;
        break;
      } else {
        ++a;
      }
    }
    if (a == A.size()) {
      break;
    }
  }

  if (b == B.size() && B[b - 1] <= A[a - 1]) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
  
  return 0;
}