首页 > 代码库 > hdu4190 简单二分
hdu4190 简单二分
题意是
有n个城市,m个投票箱,接下来n个城市人口数,每个投票箱都不能为空,计算最后投票箱的容量必须达到多少,才能满足需要。 每个城市的人必须只能将票投到自己城市分得得投票箱中。要是容量最小箱子必须得都用上
二分枚举所以的人数
#include<stdio.h> #include<string.h> #include<iostream> using namespace std; int num[500100],n,m; int judge(int x) { int s=0; for(int i=1;i<=n;i++) { s+=num[i]/x; if(num[i]%x!=0) s++;//注意所有人都得投票 } if(s>m) return 0; return 1; } int main() { int i,j; while(~scanf("%d%d",&n,&m)) { if(n==-1&&m==-1) break; int L=1,R=-1; for(i=1;i<=n;i++) { scanf("%d",&num[i]); if(num[i]>R) R=num[i]; } while(L<R) { int mid=(L+R)/2; if(!judge(mid))L=mid+1; else R=mid; } printf("%d\n",R); } return 0; }
hdu4190 简单二分
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。