问题描述：
在黑板上写了N个正整数作成的一个数列，进行如下操作：
每次擦去其中的两个数a和b，然后在数列中加入一个数a*b+1，如此下去直到黑板上剩下一个数，在所有按这种方式，最后得到的数中，最大的计作Max、最小的计做Min，则该数列的极差定义为M=Max-Min
问题分析：
通过3,5,7三个数字讨论
（3*5+1）7+1=113 ((37)+1)5+1=111 (57+1)*3+1=109
由此可见，每次取其中最小的两个数最后得到的值最大，反之每次取最大的两个数值最小
解题思路：
输入一个数组，然后copy一份,分别求Min，和Max
例如求Min，那么每次都要取最大的数:
1.首先定义全局的数组和数组副本
2.然后定义一个找数组最大数的方法，一层for，每次我都找最大的，将当前最大的数赋值给一个临时变量
以及把此时数组的下标记下来，循环结束，把下标值返回。
3.求得Min的函数：
先用findMax_i()找到一个最大值的下标，将对应值赋给a，之后把numbers[返回的最大下标]=INT_MIN
这样做的目的是下一次比较的时候，数组的这个位置是最小的，不会被取出（相当于去除它）
然后再调用一次findMax_i()，将对应值赋给b，之后将a*b+1的值赋给当前的数组，这样相当于我们把刚才求的值又放回数组中
然后在下一次循环中，再去其中最大的两个值。
循环结束标志：n==1
也就是最后的Min，我们将其从数组中取出即可
这个算法贪心在每次我都要从数组中去出最优解（最大值或最小值）
代码及说明
#include "pch.h"
#include <iostream>
#include<algorithm>
#define INT_MAX 0x7fffffff//32位2进制最大数
#define INT_MIN 0x80000000//32位2进制最小数
using namespace std;
int numbers[100];//数组
int copynumbers[100];//数组副本
int n=0;//记录数组内数字的个数
int copyn = 0;//n的副本
//从数组副本中每次都挑选最小值，并返回数组下标
int findMin_i() {
int minone = INT_MAX;
int k = 0;
for (int i = 0; i < n; i++) {
if (minone > copynumbers[i]) {
minone = copynumbers[i];
k = i;
}
}
return k;
}
//从数组中每次都挑选最大值，并返回数组下标
int findMax_i() {
int maxone= INT_MIN;
int k = 0;//记录下标
for (int i = 0; i < n; i++) {
if (maxone <numbers[i] ) {
maxone = numbers[i];
k = i;
}
}
return k;
}
//计算出Min
int getMIN(int array[], int n) {
int a;
int b;
int Max=0;
int i;//记录a的下标
int j;//记录b的下标
while(n!=1){
i = findMax_i();//获取数组中的最大值下标
a = numbers[i];//将i对应的值赋给a
numbers[i] = INT_MIN;//重置i下标的值，使得它为最小值（相当于去除它）
j = findMax_i();
b= numbers[j];//再获取数组中的最大值（注意其实它是第二大的数，第一大的数是a）
numbers[j] = a * b + 1;//将计算结果再放入其中
n--;//数组中还剩余的数（除固定值INT_MIN之外）
}
Max = numbers[findMax_i()];//获取数组中最后一个最大的数（计算的结果）
return Max;
}
//计算出Max，与Min思路一致
int getMAX(int array[], int n) {
int a;
int b;
int Min = 0;
int i;
int j;
while (n != 1) {
i = findMin_i();
a = copynumbers[i];
copynumbers[i] = INT_MAX;
j = findMin_i();
b = copynumbers[j];
copynumbers[j] = a * b + 1;
n--;
}
Min = copynumbers[findMin_i()];
return Min;
}
int main()
{
cout << "请输入数字的个数：" << endl;
cin >> n;
copyn = n;//拷贝一份
cout << "输入数字：" << endl;
for (int i = 0; i < n; i++) {
cin >> numbers[i];
copynumbers[i] = numbers[i];//拷贝一份
}
cout << "最小值为：";
int Min = getMIN(numbers,n);
cout << Min<<endl;
cout << "最大值为：";
int Max = getMAX(copynumbers, n);
cout << Max<<endl;
cout << "数列极差M=" << Max-Min<<endl;
}
运行结果：
京公网安备 11010502036488号