首页 > 代码库 > P2183 巧克力（二分答案）
P2183 巧克力（二分答案）
P2183 巧克力
题目描述
佳佳邀请了M个同学到家里玩。为了招待客人，她需要将巧克力分给她的好朋友们。她有N（1<=N<=5000）块巧克力，但是大小各不一样，第i块巧克力大小为为1*Xi（1<=i<=N,1<=Xi<=10000）
为了公平，她需要让每人所分得的巧克力大小一样，而且为了礼貌，巧克力是一整块地分给客人。所以她需要将巧克力分成大小为S的M块，而且使得S最大。但她很忙还要照顾她的客人，所以就将任务交给你了，你需要求出S。
输入输出格式
输入格式：
第一行，N，M
下接N行为N块巧克力的大小。
输出格式：
仅有一行，为巧克力大小S。
输入输出样例
输入样例#1：
Input.txt 9 5 1 2 3 4 5 6 7 8 9
输出样例#1：
Output.txt 5
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 int a[5010]; 5 int main() 6 { 7 int n,m,l=1e9,r=0; 8 scanf("%d%d",&n,&m); 9 for (int i=1; i<=n; ++i)10 {11 scanf("%d",&a[i]);12 l = min(l,a[i]); //初始l,r 13 r = max(r,a[i]);14 }15 while (l<=r) //二分 16 {17 int mid = (l+r)>>1;18 int sum = 0;19 for (int i=1; i<=n; ++i)20 sum += a[i]/mid; //数一下能切几块 21 if (sum>=m) l = mid+1;22 else r = mid-1;23 }24 printf("%d",l-1);25 return 0;26 }
P2183 巧克力（二分答案）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。