之前忙着期末考试与一些其他的闲杂事情所以就耽搁了更深层的钻研现在暑假又来补啦由于今天实在是有些晚了再加上本人脑容量不是很够所以这篇文章就写了一道题码蹄集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(l1 r) { int mid (lr) 1; if(check()) l mid; else r mid; } return r; }然后就是命值了l我仍然是选择的命值为0r命值为最大的a[i]1000000009在这个范围内去找答案同时写一个加和函数fun当加和后的结果如果大于给定的m值那么就将后就将l赋值为mid反之则将r赋值为mid最后取的是右边的值因为找最小的那么就应该在右边那些不可行的范围中找到那个边界值也就是最小的r就是我们要求的D值。代码如下#includebits/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(l1 r) { int mid (lr) 1; if(fun(mid) m) l mid; else r mid; } D r; cout D \n; } return 0; }