一月24日新生冬季练习赛解题报告C.极差

C.极差
Time Limit: 1000 MS Memory Limit: 32768 K
Total Submit: 22 (18 users) Total Accepted: 18 (18 users) Special Judge: No
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]);

    }

 

}

一月24日新生冬季练习赛解题报告C.极差

上一篇:Decode URL的工具寻找之路


下一篇:iOS 开发一年总结