自动搬运

查看原文

来自洛谷，原作者为

	chlchl AFOed.

搬运于2025-08-24 22:31:17，当前版本为作者最后更新于2021-05-29 20:39:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目及意思

题目传送门。

这道题若难以理解“嫉妒值”的意思，先别急着看题解，可以结合样例来帮助理解题目的意思。这里就先拿题目的样例来做例子分析。

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

看出来了吧？这题其实是让我们找到一种合适的方案，分给每个人之后让他们之中的最大值最小。

思路

这道题正解是二分，关键词为最大值（即嫉妒值）最小。看到这种问题的可优先考虑二分。确定核心算法后，进一步分析发现：如果每个分到弹珠的孩子都分到最多的弹珠，那么嫉妒值越大，分到弹珠的孩子越少；嫉妒值越小，分到弹珠的孩子越少。这个嫉妒值是具有单调性的，满足二分的要求。所以确定本题为二分答案。

以下为二分模板。

while(l <= r){
		mid = (l + r) / 2;
		if(check(mid)){//check 函数需要手写
			r = mid - 1;//不同题目可能这里不太一样
		}else	l = mid + 1;//同上
	}
}

若连上面的模板都不能打出来的话建议先去做一下P2249。

check函数的思路：我们需要将相同颜色的弹珠尽量按当前枚举的数量平均分给小盆友们，具体的模拟过程就是除法。我们通过二分枚举嫉妒值 mid，发现第 i 种颜色的弹珠数 $a_i$ 至少需要分给 $\left\lceil\dfrac{a_i}{mid}\right\rceil$ 个孩子。最后把每种颜色的弹珠所分得的孩子数加起来就得到最小的孩子数了。

一些小坑

1. 二分答案时，不能将 mid 直接当做答案输出，要将它的值赋给 ans，输出 ans，否则你会只有 90 分。

2. 注意二分条件和范围。

3. check 函数求每种颜色的弹珠可分得的人数时，应注意判断是否整除，如出现余数则人数应该+1，因为是向上取整.

4. 谨记：五年 OI 一场空，不开 long long 见祖宗！ 不开 long long 会 WA 两个点，只有 90 分。

代码

要什么代码，自己写嘛。

以下是参考代码，我真诚地劝大家不要抄袭。

$Code$:

#include<bits/stdc++.h>
#define ll long long
//这里意思是将long long缩写为ll，省点力气
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++;
                //也有题解写成 sum+=(a[i]+x-1)/x，是等价的
	}
	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;//等价于 /2
		if(check(mid)){//返回true意味着可以考虑更大些
			r = mid - 1;
			ans = mid;
		}else	l = mid + 1;//返回false意味着要小些
	}
	cout << ans << endl;//输出答案
	return 0;
}

最后提醒大家：自强不息才是好的学习态度，不要嫉妒别人。向优秀的人学习，改正自己的缺点，才能成就更好的自己。