首页 > 代码库 > 贪心算法练习：数列极差问题

贪心算法练习：数列极差问题

2024-07-14 01:27:09   222人阅读


在黑板上写n个正整数排成的一个数列，进行如下操作：
每次擦掉其中的两个数a和b，然后在数列里面加入一个数a*b+1，
如此循环往复直到黑板上只剩下一个数，在所有按这种操作方式
最后得到的数中，最大的记为max，最小的记min，则该数列的极差
定义为m=max-min。
输入一个正整数n，然后输入n个正整数构成一个数列。
输出这n个正整数构成的数列的极差。

  1 #include<stdio.h>  2 #include<stdlib.h>  3 long maxNumber;//整个数组里面的最大的数   4 long maxNumberIndex;  5 long max(long *a,long len);  6 long min(long *a,long len);  7   8 int main()  9 { 10     long *a,*b,n,i,maxN,minN; 11     freopen("5.in","r",stdin); 12     scanf("%ld",&n); 13     a=(long *)malloc(sizeof(long)*n); 14     b=(long *)malloc(sizeof(long)*n); 15     for(i=0;i<n;i++) 16     { 17         scanf("%ld",a+i); 18         b[i]=a[i]; 19     } 20     minN=min(b,n);//注意：必须先调用min（）函数再调用max（）函数  21     maxN=max(a,n); 22     //printf("%ld %ld\n%ld\n",maxN,minN,maxN-minN); 23     printf("%ld\n",maxN-minN); 24     return 0; 25 } 26 long max(long *a,long len)//返回相乘结果最大的那个乘积  27 { 28     long i,min1,min2,min1Index,min2Index,m;//min1,min2表示最小和次小的两个数的值。min1Index和min2Index表示最大和次大的两个数的下标  29     //注意：数组a里面最小和次小的两个数可以是一样大小，但不可能是下标相同的两个数 . 30     while(len>1) 31     { 32         min2=min1=maxNumber; 33         min2Index=min1Index=maxNumberIndex; 34         for(i=0;i<len;i++) 35         { 36             if(a[i]<min1) 37             { 38                 min2=min1; 39                 min2Index=min1Index; 40                 min1=a[i]; 41                 min1Index=i; 42             } 43             else if(a[i]<min2) 44             { 45                 min2=a[i]; 46                 min2Index=i; 47             } 48         } 49         m=min1*min2+1; 50          51         if(min1Index>min2Index) 52         { 53             a[min2Index]=m; 54             if(m>maxNumber) 55             { 56                 maxNumber=m;//更新当前数组里面的最大值  57                 maxNumberIndex=min2Index; 58             } 59             a[min1Index]=a[len-1]; 60             len--; 61         } 62         else  63         { 64             a[min2Index]=a[len-1]; 65             a[min1Index]=m; 66             if(m>maxNumber) 67             { 68                 maxNumber=m;//更新当前数组里面的最大值  69                 maxNumberIndex=min1Index; 70             } 71             maxNumberIndex=min1Index; 72             len--; 73         } 74     } 75     return a[0]; 76 } 77 long min(long *a,long len)//返回相乘结果最小的那个乘积  78 { 79     long i,max1,max2,max1Index,max2Index,m;//max1,max2表示最大和次大的两个数的值。max1I和max2I表示最大和次大的两个数的下标  80     //注意：数组a里面最大和次大的两个数可以是一样大小，但不可能是下标相同的两个数 . 81     int f=0; 82     while(len>1) 83     { 84         max2=max1=-1; 85         max2Index=max1Index=-1; 86         for(i=0;i<len;i++) 87         { 88             if(a[i]>max1) 89             { 90                 max2=max1; 91                 max2Index=max1Index; 92                 max1=a[i]; 93                 max1Index=i; 94             } 95             else if(a[i]>max2) 96             { 97                 max2=a[i]; 98                 max2Index=i; 99             }100         }101         m=max1*max2+1;102         if(f==0)103         {104             maxNumber=max1;//保存整个数组的最大值，以便在调用max()函数的时候方便寻找最小的两个数。 105             maxNumberIndex=max1Index;106             f=1;107         }108         if(max1Index>max2Index)109         {110             a[max2Index]=m;111             a[max1Index]=a[len-1];112             len--;113         }114         else 115         {116             a[max2Index]=a[len-1];117             a[max1Index]=m;118             len--;119         }120     }121     return a[0];122 }
View Code

 


联系
我们