2024年3月14日发(作者：)
最大最小差()
现在有N个正整数，每一次去掉其中2个数a和b，然后加入一个数a*b+1，
这样最后只剩下一个数p。要求求出最大的p记为maxp，最小的p记为minp，
和他们的差K=maxp-minp。
任务
对于给定的数列，编程计算出它的max,min和K。
输入
输入数据的第一行是一个正整数数N（3〈=n〈=2000）表示数列的长度。接
下来的一行共N个正整数（1〈=n〈=32767 ），为数列中的数。
输出
输出数据共三行，分别输出MAX，MIN，K
样例输入
3
1 1 1
样例输出
3
3
0
算法分析：
这是一个古老的贪心问题。
如果要最终的数字最大，那么对于每一步应该去掉最小的两个数。
类似的，如果要最终的数字最小，那么对于每一部应该去掉最大的两个数。
算法实现：
由于本题的规模很大，光是高精度计算就要消耗不少的时间，所以说相对于
高精度计算，每次找两个最大（或最小）数的时间与高精度比起来要小很多，因
此，本题的优化关键不在于时间，而是空间。
如果用常规的二维表来保存高精度的值，至少要2000*2000*5的空间，注意
到无论怎么样选数，当前剩下数的位数和肯定不会比最初的位数和大很多。而最
初的N个数最多也就2000*5位，因此，只要合理的利用空间，空间上同样不会
存在问题。因此，我们可以用动态数组来保存数列，并且利用GETMEN函数，
根据当前的需要来申请空间，每次去掉两个数，就将这两个数占有的空间释放，
并重新申请新数的空间。如此一来，空间上就不存在什么问题了。
小优化：
假定输入的数按从大到小排序后为A1、A2……AN，如果要求最小数，显
然先去掉A1、A2，然后写上A1*A2+1，由于输入的都是正整数，因此，A1*A2+1
还是最大的数。利用这一规律，在求最小数的时候也就无需用一个N*N的算法
来寻找每一步的两个最大数了，直接从数组中调用即可。这样算法的复杂度可以
有所下降，但是不能在本质上起到优化的作用。
小结：
本题很经典，只要知道用贪心来做，并且想到GETMEM函数的话，要解决
它还是很容易的。
数据分析：
发布者：admin，转转请注明出处：http://www.yc00.com/web/1710371267a1745444.html
评论列表（0条）