[COCI2012-2013#1] LJUBOMORA

题目描述

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

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

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

输入格式

输入共 $M+1$ 行。

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

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

输出格式

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

样例 #1

样例输入 #1

5 2
7
4

样例输出 #1

3

样例 #2

样例输入 #2

7 5
7
1
7
4
4

样例输出 #2

4

提示

【数据范围】

对于 $100\%$ 的数据，保证 $1\le M\le 3\times 10^5$，$1\le N\le 10^9$，$M\le N$。

【说明】

本题分值按 COCI 原题设置，满分 $120$。

题目译自 COCI2012-2013 CONTEST #1 T4 LJUBOMORA。

C++实现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 300000 + 10;
ll n, m, l, r, ans, mid, a[N];
bool check(ll x){
ll sum = 0;
for(int i=1;i<=m;i++){
sum += a[i] / x;
if(a[i] % x != 0) sum++;
}
return sum <= n;
}
int main(){
cin >> n >> m;
for(int i=1;i<=m;i++){
cin >> a[i];
r += a[i];
}
while(l <= r){
mid = (l + r) >> 1;
if(check(mid)){
r = mid - 1;
ans = mid;
}else l = mid + 1;
}
cout << ans << endl;
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容