BOJ 16981 - Exhibition

BOJ 16981 - Exhibition

일단 $V_i$ 와 $C_j$ 에 대해 각각 두개를 정렬한다.

이제 문제는 $S_i$ 중 $C_i$ 에 들어갈 수 있는 가장 긴 수열을 찾는 문제가 된다.

$C$ 는 정렬되어 있으므로 다음과 같이 그리디를 시행할 수 있다.

$i=N-1 \to 0$ 으로 진행한다.

현재 정답이 $a$ 일 때, $C_{m-a-1} \ge S_i$ 라면 정답을 $1$ 늘린다.

프레임을 최대한 많이 소모하는 것이 목적이기 때문에 단순하게 이렇게 하면 된다.

남은 프레임 중, 큰 프레임부터 보면서 현재 $S_i$ 이상이라면 매칭시켜주면 된다.

void solve() {  
   int n, m;  
   cin >> n >> m;  
   vector<pi> a(n);  
   for (auto &[s, v]: a) cin >> s >> v;  
   vi c(m);  
   fv(c);  
   sort(all(c));  
   sort(all(a), [&](auto &a, auto &b) {  
      if (a.se ^ b.se) return a.se < b.se;  
      return a.fi < b.fi;  
   });  
   vi b;  
   for (int i = 0; i < n; i++) b.pb(a[i].fi);  
  
   int ans = 0;  
   for (int i = n - 1; i >= 0 && ans < m; i--) {  
      if (c[m - ans - 1] >= b[i]) ans++;  
   }  
   cout << ans;  
}