CFR 466 B. Wonder Room ( Square root decomposition, Math )

Problem - B - Codeforces

題意：
有 n 個人，現有一個 a * b 的土地。可以任意伸長寬和高，希望面積不小於 6 * n 的前提下，面積最小，求最小面積和對應的長寬。

資料規模：
n, a, b ≤ 1e9
TL: 1000 ms

解法：
不失一般性假設 a ≤ b，顯然最佳解的 a 的上界為 ceil( sqrt( 6 * n ) )。因此考慮枚舉。

時間 / 空間複雜度：
O( n ^ 0.5 )

#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main(){
  ios::sync_with_stdio( 0 );
  int n, a, b; cin >> n >> a >> b;
  if( 1LL * a * b >= 6LL * n ){
    cout << 1LL * a * b << endl;
    cout << a << " " << b << endl;
    exit( 0 );
  }
  int stag = 0;
  if( not ( a <= b ) ) stag = 1, swap( a, b );
  int lim = sqrt( 6LL * n ) + 1;
  long long ans = 1LL * lim * lim;
  int x = max( a, lim ), y = max( b, lim );
  for( int i = a; i <= lim; ++i ){
    int j = max( 1LL * b, ( 6LL * n + i - 1 ) / i );
    if( 1LL * i * j <= ans ){
      ans = 1LL * i * j;
      x = i, y = j;
    }
  }
  cout << ans << endl;
  if( stag ) swap( x, y );
  cout << x << " " << y << endl;
  return 0;
}