XJTUOJ #1078 JM的恶有恶报

题目

https://oj.xjtuicpc.com/problem/1078

思路

简单的二分答案题。其实，涉及到分配问题的，最优决策难以确定的题，很有可能是二分题。这也算是个套路吧。

代码

#include<cstdlib>
#include<algorithm>
#define maxm (int)(1e5+10)
#define inf 0x3f3f3f3f
using namespace std;
int a[maxm],n,m;
bool check(int x){
	int i,cnt=0;
	if(!x) return true;
	for(i=1;i<=m;i++)
		cnt+=a[i]/x;
	return cnt>=n;
}
int main(){
	int i,j,l=0,r=0,ans;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;++i){
		scanf("%d",&a[i]);
		r=max(r,a[i]);
	}
	while(l<=r){
		int mid=l+r>>1;
		if(check(mid)){
			ans=mid;
			l=mid+1;
		}
		else r=mid-1;
	}
	printf("%d",ans);
	// system("pause");
	return 0;
}