526互联

[COCI2012-2013#1] LJUBOMORA

发布时间 2023-05-25 14:26:58作者: o-Sakurajimamai-o

LJUBOMORA:
这题本来用的数学方法把样例全给过了,没想到交了一下全WA了(呜呜

# [COCI2012-2013#1] LJUBOMORA

## 题目描述

一家弹珠厂向一所幼儿园捐赠了一些弹珠，弹珠一共有 M 种颜色，每颗弹珠都有一种颜色。老师需要把所有的弹珠分给 N 个孩子。每个孩子得到的所有弹珠都必须是**相同的颜色**，而且可以有一些孩子一颗弹珠也没得到。

我们把**嫉妒值**定义为分给一个孩子最多的弹珠数量。请你帮助老师分弹珠，使得嫉妒值**最小**。

例如，如果有 4个红色的弹珠（RRRR）和 7个蓝色的弹珠（BBBBBBB），要分给 5个孩子，那么我们可以这样划分：RR，RR，BB，BB，BBB。这样分的嫉妒值为 3，是最小的。

## 输入格式

输入共 M+1行。

第一行包含两个正整数 $N,M$，分别表示孩子数和弹珠的颜色总数。

接下来 $M$ 行的第 $i$ 行包含一个正整数 $x$（$x \in [1,10^9]$），表示有 $x$ 个颜色为 $i$ 的弹珠。

## 输出格式

输出一行一个整数，表示最小的嫉妒值。

二分查找经典题,还是经典的最大值最小,建立check函数,然后查找到一个最小值

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 long long a[100000010],n,m,res,r;
 4 bool check(long long x)
 5 {
 6     long long num=0;
 7     for(int i=0;i<m;i++)
 8     {
 9         num+=a[i]/x;
10         if(a[i]%x!=0) num++;
11     }
12     return num<=n;
13 }
14 int main()
15 {
16     cin>>n>>m;
17     for(int i=0;i<m;i++) cin>>a[i],r+=a[i];
18     long long l=1;
19     while(l<=r)
20     {
21         long long mid=(l+r)>>1;
22         if(check(mid))
23         {
24             r=mid-1;
25             res=mid;
26         }
27         else l=mid+1;
28     }
29     cout<<res;
30     return 0;
31 }