二分
查看原帖
二分
270854
二叉苹果树楼主2022/10/11 23:27

快考第二轮了才想起来自己不会二分,不会DP,不会高精度,不会搜索

能具体讲讲while里的条件和 llrr 的赋值嘛,比如

while(l<=r)
while(l<r)
l=mid+1
l=mid
r=mid-1
r=mid
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
int n,m,a[MAXN],l,r;
bool check(int sum)
{
	int ans=0;
	for(int i=1;i<=n;i++)
	    ans+=a[i]/sum;
	return ans>=m;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
	    cin>>a[i];
	    r+=a[i];
	    l=1;
	}
	if(r/m==0)
	{
		cout<<0<<endl;
		return 0;
	}
	l=0,r=100000000;
	while(l+1<r)
	{
	    int mid=l+r>>1;
	    if(check(mid))
	        l=mid;
	    else
	        r=mid; 
	}
	cout<<l<<endl; 
	return 0;
}
2022/10/11 23:27
加载中...