| C.极差 | |||||
|
|||||
| Description | |||||
| 小辉是个顽皮的胖孩纸，总爱在老师的黑板上乱涂乱画，又一次他在老师的黑板上写了有n个正数组成的数列，这时小彪看见了，就说：“小胖子，就用黑板上的这些数，我考你一道题，你每次选中这些数的其中两个数a和b，然后将它们擦掉，再在黑板上写上a*b+1，直到剩下最后一个数。。。如果你能得到最小的数min和最大的数max,并求出max-min，我就给你买煎饼果子吃。” 听到了好吃的，小辉两眼放光，可是这种费脑细胞的问题小辉不会，请你来帮帮他。。。 | |||||
| Input | |||||
| 有多组测试数据，每组数据第一行是数列长度n（2<=n<=20），第二行是小辉所写的数列,最大值保证不超过int，输入处理到文件结束。 | |||||
| Output | |||||
| 输出max-min的值并换行。 | |||||
| Sample Input | |||||
|
2
1 2
6
4 3 5 1 7 9
|
|||||
| Sample Output | |||||
|
0
1688
|
|||||
| Hint | |||||
水体一枚
直接上代码：
额 代码删了
我说点值得注意的地方吧
每次变换数字之后都要排序才可以
同样是杭电的思路：
贪心
做两次贪心，分别得到最大值和最小值
对所有提供的数排序，然后合并两个最大的，在剩下的数（包括合并后得到的数）中继续取两个最大的合并，这样能得到最小值
对所有提供的数排序，然后合并两个最小的，在剩下的数（包括合并后得到的数）中继续取两个最小的合并，这样能得到最大值
然后最大值和最小值做差就得到结果了
代码如下：
# include <stdio.h>
# include <iostream>
# include <algorithm>
using namespace std;
int main ()
{
int a[22],b[22];
int n,i;
while(scanf("%d",&n)!=EOF)
{
for(i=0; i<n; i++)
{
scanf("%d",&a[i]);
b[i]=a[i];
}
for(i=0; i<n-1; i++) //max
{
sort(a+i,a+n);
a[i+1]=a[i]*a[i+1]+1;
}
for(i=n-1; i>0; i--) //min
{
sort(b,b+i+1);
b[i-1]=b[i]*b[i-1]+1;
}
printf("%d ",a[n-1]-b[0]);
}
}