我们首先只考虑一组数据
76 3 //注意,与题目所给数据不同
为了方便说明,我们将题意稍微修改一下,我们有76个小朋友,要分成恰好3组,问每组的小朋友的人数范围?
那么很方便类比
上限:76/3=25,每组最多有25个人,且多出来一个人
下限:我们想,要分成四组,每组最多可以有多少人?
很明显,类比上限算法,76/4 = 19 ,那么我们把每组的人数从19多加一位到20,那么我们有的组数从4组降到3组,得到要分成三组,每组最少需要20人
最后我们得到每组合法的区间应该在【O / (X + 1) + 1 , O / X】
题目有N组数据那么把所有区间取个交集就是答案!
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int n;
scanf("%d", &n);
int v_min = 1, v_max = 1e9;
while (n -- )
{
int a, b;
scanf("%d%d", &a, &b);
v_min = max(v_min, a / (b + 1) + 1);
v_max = min(v_max, a / b);
}
printf("%d %d\n", v_min, v_max);
return 0;
}