백준 20033 - Square, Not Rectangle

https://www.acmicpc.net/problem/20033

 

얼마나 큰 정사각형을 만들 수 있는지를 물어보므로 결정할 수 있는 높이 H를 다음 함수를 사용하여 구할 것이다.

 

$f(H) = $ 높이가 $H$일 때 길이가 $H$ 이상인 선분을 구할 수 있는지의 여부

 

그러면 $f(H)$의 치역은 true 혹은 false로 결정될 수 있고 true라면 $H$를 더 크게, false라면 $H$를 더 작게 잡을 수 있다.

 

여기서 파라메트릭 서치를 사용하면 $f(H) = True$인 $H$의 최댓값을 빠르게 구할 수 있고 문제의 목적은 정사각형을 만드는 것이므로 이렇게 구한 $MAX(H)$가 답이다.

 

따라서 우리는 $f(H)$를 구할 때 $H$ 이상의 너비를 확보할 수 있는지 구하면 된다.

 

구현

#pragma GCC target("fma,avx,avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
 
#include "bits/stdc++.h"
// #include "ext/pb_ds/assoc_container.hpp"
 
using namespace std;
// using namespace __gnu_pbds;
 
using ll = int_fast64_t;
using pii = pair<int, int>;
// using oset = tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
 
constexpr int MXN = 300001;
int n;
int ar[MXN];
 
void solve()
{
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    cin >> ar[i];
  }
 
  int lo = 1, hi = n;
  int ans = -1;
 
  while (lo <= hi)
  {
    int mid = lo + (hi - lo) / 2;
    int len = 0;
    int wow = 0;
    for (int i = 0; i < n; i++)
    {
      if (ar[i] >= mid)
      {
        ++len;
      }
      else
      {
        wow = max(len, wow);
        len = 0;
      }
    }
 
    wow = max(wow, len);
 
    bool accepted = wow >= mid;
 
    if (accepted)
    {
      ans = mid;
      lo = mid + 1;
    }
    else
    {
      hi = mid - 1;
    }
  }
 
  cout << ans;
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}