码蹄杯冲刺！！！

之前忙着期末考试与一些其他的闲杂事情所以就耽搁了更深层的钻研，现在暑假又来补啦！由于今天实在是有些晚了，再加上本人脑容量不是很够，所以这篇文章就写了一道题码蹄集OJ-丫鬟的月例银。

MC0481丫鬟的月例银 难度：黄金

年终结算时，贾母发现各房主子丫鬟的月例银总额太高了。为了削减开支，需要进行调整。现在假设荣国府一共有n个丫鬟，她们的月例银排成正整数序列为a1∼an​。现在削减开支的目标，是要让这n个数字之和不超过m。

为了实现这一目标，小码妹可以钦定一个正整数D，使得所有的ai​变成⌊ai/D⌋，现在问，要实现这一目标，D最小可以是多少（当然不能小于1）？

格式

输入格式：

第一行一个整数T(1≤T≤5×100000)，表示测试数据组数，对于每组测试数据：
第一行两个整数n,m(1≤n≤5×100000,1≤m≤1000000000000)。
第二行nn个整数a1∼an(1≤ai≤1000000000)。
数据保证 ∑n≤5×1000000。

输出格式：

对于每组测试数据，一行一个整数，表示答案。

样例 1

输入：

3 5 10 10 10 4 10 6 5 10 1 1 1 1 1 5 10 2 2 3 2 2

复制

输出：

4 1 2

复制

样例 2

输入：

1 1 1 999999999

输出：

500000000

本题相关知识点： 算法基础：二分 | 三分

思考

这个题一开始看到的时候我脑子还有点雾水，但是看到了算法基础是二分我就瞬间明白可以怎么来进行思考了。（虽然但是，希望自己在比赛时也能看出这个找最小值是用二分）

要找到可以满足每一个月例银除掉一个最小值后加起来还要小于一个m值的D值，此时我们使用二分就能避免数据过多而导致的超时了。当然，这个二分模板我仍然选择的是自己用的比较熟练的，详细见下方。

int find(int q) { int l = 0, r = 最大值； while(l+1 < r) { int mid = (l+r) >> 1; if(check()) l = mid; else r = mid; } return r; }

然后就是命值了，l我仍然是选择的命值为0，r命值为最大的a[i]1000000009，在这个范围内去找答案，同时写一个加和函数fun，当加和后的结果如果大于给定的m值，那么就将后就将l赋值为mid，反之则将r赋值为mid，最后取的是右边的值，因为找最小的，那么就应该在右边那些不可行的范围中找到那个边界值也就是最小的r，就是我们要求的D值。

代码如下：

#include<bits/stdc++.h> #define N 500005 using namespace std; int n, D; long long a[N], m, sum; long long fun(int x) { long long tmp = 0; for(int i = 1; i <= n; i++) { tmp += a[i]/x; } return tmp; } int main( ) { int T; cin >> T; while(T--) { cin >> n >> m; for(int i = 1; i <= n; i++) { cin >> a[i]; sum += a[i]; } if(sum <= m) { cout << 1 << '\n'; sum = 0; continue; } int l = 0, r = 1000000009; while(l+1 < r) { int mid = (l+r) >> 1; if(fun(mid) > m) l = mid; else r = mid; } D = r; cout << D << '\n'; } return 0; }