洛谷—— P2183 巧克力

时间：2021-06-20 06:53:11

https://www.luogu.org/problemnew/show/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

 #include <algorithm>

 #include <cstdio>

 inline void read(int &x)

 {

     x=; register char ch=getchar();;

     for(; ch>''||ch<''; ) ch=getchar();

     for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';

 }

 int n,m,a[];

 int L,R,Mid,ans;

 inline bool check(int x)

 {

     int cnt=;

     for(int i=n; i; --i)

     {

         if(cnt>=m) return ;

         cnt+=a[i]/x;

     }

     return false;

 }

 int Presist()

 {

     read(n),read(m);

     for(int i=; i<=n; ++i) read(a[i]);

     std:: sort(a+,a+n+);

     for(R=a[n]; L<=R; )

     {

         Mid=L+R>>;

         if(check(Mid))

         {

             ans=Mid;

             L=Mid+;

         }

         else R=Mid-;

     }

     printf("%d\n",ans);

     return ;

 }

 int Aptal=Presist();

 int main(int argc,char**argv){;}

相关文章