CFR 449 A. Jzzhu and Chocolate ( Math, Sqrt Decomposition )

Problem - 449A - Codeforces

題意：
給一個 n * m 的巧克力板，要割 k 次，每次只能割還沒割過的整數水平線或鉛直線，求最小的塊面積最大可以為何。

測資規模：
A single line contains three integers n, m, k (1 ≤ n, m ≤ 1e9; 1 ≤ k ≤ 2e9).

解法：
貌似有數學 O( 1 ) 解，但我不會。
想清楚題目所求，其實是，令 x 為最佳解的水平切割次數，y 為最佳解的鉛直切割次數，那麼所求為 floor( n / x ) * floor( m / y )。又考慮到，floor( n / x ) 的可能值範圍只有至多 2 * n ^ 0.5 個值，因此可以暴力枚舉。

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

signed main(){
  ios::sync_with_stdio( 0 );
  int n, m, k; cin >> n >> m >> k;
  if( n - 1 + m - 1 < k ){
    cout << -1 << endl;
    exit( 0 );
  }
  long long ans = 0;
  for( int i = 1; i * i <= n; ++i ){
    int floor_x = n / i; // how many parts
    int max_x = n / floor_x - 1; // maximum cut
    int min_y = max( 0, k - max_x ); // minimum cut
    if( min_y + 1 <= m ){
      ans = max( ans, 1LL * floor_x * ( m / ( min_y + 1 ) ) );
    }
  }
  for( int i = 1; i * i <= n; ++i ){
    int floor_x = i; // how many parts
    int max_x = n / floor_x - 1; // maximum cut
    int min_y = max( 0, k - max_x ); // minimum cut
    if( min_y + 1 <= m ){
      ans = max( ans, 1LL * floor_x * ( m / ( min_y + 1 ) ) );
    }
  }
  cout << ans << endl;
  return 0;
}