可能是对于小木棍这种题目过于熟悉,把我以前在洛谷P2440上的代码搬来了,ac了
讲讲思路:二分的基础题目
二分最重要的就是check函数 (这仅仅只是可行解)
当然可行解并不一定是最优解所以我们还需要往最优解靠继续二分
#include <bits/stdc++.h> using namespace std; #define int long long const signed maxn=1e6+7; int a[maxn]; int n,m; bool check(int x) { int cnt=0; for (int i=1;i<=n;++i) { cnt+=a[i]/x;统计总共可以得到多少根 if (cnt>=m)///所得数大于预估 return 1;//说明这是可行解 } return 0; } signed main() { scanf("%lld%lld",&n,&m); int mmaxn=0; for (int i=1;i<=n;++i) { scanf("%lld",a+i); mmaxn=max(mmaxn,a[i]); } int l=1; int r=mmaxn;///从最大的那一段开始二分 while (l<=r) { int mid=(l+r)>>1; if (check(mid)) l=mid+1; else r=mid-1;///比预估少 所以区间向左移 } printf("%lld",l-1);///最后满足的是l=mid+1 此时的mid就是答案因为check的是mid return 0; }