Time cost:35min
题意:给n根绳子 问切成k段的最大长度
妥妥的二分 能切成长的一定能切成短的
所以就O(lgV)二分 * O(n)判断能切成多少段
如果能切不少于k就L=m 否则R=m
Code:
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 #define rep(i,a,n) for(int i = a;i <= n;++i) 6 #define per(i,n,a) for(int i = n;i >= a;--i) 7 #define ms(a,b) memset(a,b,sizeof a) 8 #define eps 1e-5 9 using namespace std; 10 typedef double D; 11 int read() { 12 int as = 0,fu = 1; 13 char c = getchar(); 14 while(c < '0' || c > '9') { 15 if(c == '-') fu = -1; 16 c = getchar(); 17 } 18 while(c >= '0' && c <= '9') { 19 as = as * 10 + c - '0'; 20 c = getchar(); 21 } 22 return as * fu; 23 } 24 //head 25 const int N = 10006; 26 int n,k; 27 D a[N],maxx; 28 D L,R; 29 bool check(D l) { 30 int ans = 0; 31 rep(i,1,n) ans += int(a[i] / l); 32 return ans >= k; 33 } 34 35 int main() { 36 n = read(); 37 k = read(); 38 rep(i,1,n) scanf("%lf",&a[i]),maxx = max(maxx,a[i]); 39 L = 0,R = maxx; 40 while(R - L > eps) { 41 D m = (L + R) / 2.000; 42 check(m) ? L = m : R = m; 43 } 44 printf("%.2lf ",floor(R*100)/100); 45 return 0; 46 }