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 | |||||
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\n",a[n-1]-b[0]);
}
}