#include<bits/stdc++.h> using namespace std; int a[100005]; int n,k; bool check(int mid){ int sum = 0; for(int i = 1;i <= n;i++){ sum += a[i] / mid; } return sum >= k; } int main(){ cin >> n >> k; for(int i = 1;i <= n;i++) cin >> a[i]; int l = 1,r = 1e8; int ans = 0; while(l <= r){ int mid = l + r >> 1; if(check(mid) == true){ ans = mid; l = mid + 1; }else{ r = mid - 1; } } cout << ans; return 0; }

二分答案

保过

题意要求我们把木材切割成很多段，使得这个短段尽量的长。 我们切割的段肯定是在[ 0,max{ wood [ i ] } ]中，满足二分的有界性。 由题意显然单调，满足单调性。所以可以使用二分答案求解。 如果发现能切够k段则去右半部分找更大的解，如果发现切不够k段就去左边找可行解。

#include<bits/stdc++.h> using namespace std; int n,m,a[10000009]; bool sum(int x){ long long s=0; for(int i=1;i<=n;i++){ s+=a[i]/x; } return s>=m; } int main(){ cin>>n>>m; int l=1,r=0,ans=0; for(int i=1;i<=n;i++){ cin>>a[i]; r=max(r,a[i]); } while(l<=r){ int mid=(l+r)/2; if(sum(mid)){ ans=mid; l=mid+1; } else r=mid-1; } cout<<ans; return 0; }