You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.
# include <bits/stdc++.h>
using namespace std ;
const int N = 110 ;
const int INF = 0x3f3f3f3f ;
int n , k ;
int w [ N ] , h [ N ] ;
int tmax = - INF ;
/*
2 6
4 3
5 4
答案：
2
*/
// 检查x是否满足某种性质
bool check ( int x ) {
int cnt = 0 ;
for ( int j = 1 ; j < = n ; j + + )
cnt + = ( w [ j ] / x ) * ( h [ j ] / x ) ;
//以2为例，
//以1为例 cnt=32 k=6 cnt>k
//所以最终的限制条件为cnt<=k
return cnt < = k ;
}
int main ( ) {
cin > > n > > k ;
for ( int i = 1 ; i < = n ; i + + ) {
cin > > w [ i ] > > h [ i ] ;
tmax = max ( min ( w [ i ] , h [ i ] ) , tmax ) ;
}
//二分查询
int l = 1 , r = tmax ;
while ( l < r ) {
int mid = l + r > > 1 ;
if ( check ( mid ) )
r = mid ;
else
l = mid + 1 ;
}
//也可能找不到答案
int cnt = 0 ;
for ( int i = 1 ; i < = n ; i + + )
cnt + = ( w [ i ] / l ) * ( h [ i ] / l ) ;
if ( cnt < k )
cout < < - 1 < < endl ;
else
cout < < l < < endl ;
return 0 ;
}
