题意

SDUQD 旁边的滨海公园有 x 条长凳。第 i 个长凳上坐着 a_i 个人。这时候又有 y 个人将来到公园，他们将选择坐在某些公园中的长凳上，那么当这 y 个人坐下后，记k = 所有椅子上的人数的最大值，那么k可能的最大值mx和最小值mn分别是多少。

Input

第一行包含一个整数 x (1 <= x <= 100) 表示公园中长椅的数目
第二行包含一个整数 y (1 <= y <= 1000) 表示有 y 个人来到公园
接下来 x 个整数 a_i (1<=a_i<=100)，表示初始时公园长椅上坐着的人数

Output

输出 mn 和 mx

输入样例

3
7
1
6
1

输出样例

6 13

提示

最初三张椅子的人数分别为 1 6 1
接下来来了7个人。
可能出现的情况为{1 6 8},{1,7,7},…,{8,6,1}
相对应的k分别为8,7,…,8
其中，状态{1,13,1}的k = 13，为mx
状态{4,6,5}和状态{5,6,4}的k = 6，为mn

分析

这道题可以用贪心算法来解决。

• 题目分析

【好久没有写这种一来就能直接分析题目的题了呜呜呜】

理解这道题的关键是提示中的样例解释。其中提到的可能出现的情况是指，将新增加的人数随机分配到每一张长凳上任意数量的所有情况。而最大和最小最大值就是所有情况所得长凳人数最大值的最大和最小值。

显然，最简单的办法就是求出所有情况，遍历所有情况即可得到答案。但是求出所有情况真的容易实现吗？当长凳数量和新增人数都较小时，可以通过穷举所有情况来获得答案。可这两个数据中任意一个增大时，求出所有情况都将变得很困难。

那么换种思路，一定有一个简单的规律或者准则，使得我们能够直接求得我们想要的那一种情况，也就是包含答案的情况。

• 最大最大值

这个比较简单。可以想到，由于长凳人数没有限制，将新增人数加到原最大值上，显然这种情况下所得一定是新的最大值，且没有第二种情况，否则将与原最大值相矛盾。

如果当人数有限制时，这道题就会变复杂啦。

• 最小最大值

1）二分 / 最小生成树 ❌
当看到这两个名词出现时，脑海中首先浮现的其实是二分法以及最小生成树????[week6] (CSP201812-4)数据中心——最小生成树

但是这道题的数据结构并不是树结构，各点是独立的，彼此之间没有关联。并且，求最大最值和最小最值的二分法需要有一个大致的范围，但是在这道题中，最小最值的范围很难界定，如果太大显然是浪费时间且不合理的。同时，如何在确定一个最小最值时验证其的正确性呢？【可以去想一下】

2）搜索法❌

不知道为什么，我又想到了隐式图问题。是否可以通过dfs或是bfs实现求解所有情况呢？但是当着手开始写的时候就会发现，这个不行。可以走的分岔路过多，情况较多，如何递归或压入队列，需要有明确的条件。那这个条件又是什么呢？

3）贪心算法✅

当想到这里的时候，我的脑海中已经有比较清晰的思路了。

其实这道题算是没那么复杂的贪心算法。只要理清思路就可以快速解出。

• 特殊情况

在最开始草稿演算时，我就有想到，如果把所有新增人数一个人一个人地去分配。但是彼时并没有完全想明白，不过倒是发现了求解最小最大值的特殊情况：

最小最大值为原最大值

因为人数在增多，因此最大值的最小只能为原最大值。而这代表在其对应的情况中，其余的所有值仍然不大于原最大值。

1. 当新增人数与原最小值相加都小于原最大值
   只要这种情况成立，就代表着除去改变的原最小值外，其余所有的值不变，仍然小于原最大值。而此时唯一变大的值却仍然不比原最大值大，因此毫无疑问，原最大值为最小最大值。
2. 当长凳数比新增人数大时❌
   在大多数情况中这代表着，可以将新增人数分为一人一组，不重复地分配到除去原最大值的任意长凳上。显然，即使存在一个长凳原人数最接近最大值，但是在分配到这一个人后，只可能是改变为等于原最大值。因为原人数中最接近最大值的人数只可能是比最大值少1。
   但是，存在特殊情况反驳该判断：存在n个长凳，其中除去第一个，其余n-1个长凳都为最大值，那么如果新增m个人(n>m>1），显然最小最大值不是原最大值。

• 贪心准则

为了使最大值最小，就要尽量让最大值靠近原最大值。也就是说要首先尽力让所有数都比最大值小或差最小。

而这代表着，在除去最大值之外的长凳中，仍然存在可以继续添加人的长凳，则应该先让这些长凳增加人数。

当有数等于或超过原最大值时，就要将还没有分配完的人分到目前仍然小于原最大值的长凳，使得当前最大值的增加最少。

总结一下，这代表着：每次都将一个人分配到当前人数最少的长凳上。若存在长凳人数超过原最大值，则更新最大值；若仍然大于更新的最大值，则继续更新。最后所得答案一定是最小最大值。

????为什么最大值一定是由选出的当前最小值新增后的数更新？
假设当前除去最大值外，所有数都小于或等于最大值。当取出当前最小值时，若该值+1仍然小于或等于最大值，那么该新值和其余没有改变的值都仍然没有超过最大值；反之，若该值+1大于最大值，但此时其他值并没有改变。因此，这就意味着，最大值只可能被增加的数更新，而增加的一定是当前的最小值。

• 代码实现

代码实现很简单：

1. 用最小堆存储所有长凳的人数，优化排序和查找最小数的时间
2. 贪心算法一共执行新增人数次。也就是说，在每一次循环时分配一个人，直到所有人分配完

总结

1. 第一次体验一次ac的快乐????太感人了，这样的题多做点其实挺有意思的，也是回顾所学知识的好机会

代码

//
//
main.cpp
//
lab3
//
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
using namespace std;
//vector<int> people;
priority_queue<int, deque<int>, greater<int>> people;
//小根堆
int main()
{
ios::sync_with_stdio(false);
int x = 0,come = 0,n = 0,max = 0,max2 = 0;
cin>>x>>come;
for( int i = 0 ; i < x ; i++ )
{
cin>>n;
people.push(n);
if( n > max )
//记录最大值
max = n;
}
//
sort(people.begin(), people.end());
max2 = max;
//初始化为原最大值，因为在贪心算法中，首先得出现大于原最大值的最大值，才有可能有新的最小最大值
//若最小值加上新增数都不大于原人数最大值，则最小最大值即为原人数最大值
//若长凳数正好等于新增数+1，则说明最小最大值仍然为原人数最大值（错误）
if( come + people.top() <= max )
//特殊情况
cout<<max<<" ";
else
//其他情况
{
for( int i = 0 ; i < come ; i++ )
//每次在当前人数最少的长凳上增加一个人
{
int min = people.top();
//得到当前人数最少的长凳
people.pop();
min++;
//增加一个人
if( min > max2 )
//更新最大长凳人数
max2 = min;
people.push(min);
//将该长凳放回小根堆中
}
cout<<max2<<" ";
}
//若除去当前最大值，其他所有长凳都没有超过最大值，则下一个可能超过最大值的一定是下一个+1的长凳，即为当前取出的最小长凳
//每一次都在人数最少的长凳上加一个人，贪心算法，使得其他更大的长凳尽量不受影响，直到少的长凳与较大的长凳人数相同或更大
cout<< max + come;
//最大最大值一定是所有人都坐到了同一张凳子上
return 0;
}

最后

以上就是甜美钻石为你收集整理的[week9]签到题（长凳）——贪心算法题意分析总结代码的全部内容，希望文章能够帮你解决[week9]签到题（长凳）——贪心算法题意分析总结代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。