poj 1862 贪心

本文主要是介绍poj 1862 贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：从N个数任取两个数按2*sqrt(a*b)合成新数放回，求最后那个数的最小值。

思路：贪心，每次取最大的2个数，计算结果后，再放回原来的数列中区，再排序，再取最大2个数，一直进行到只剩1个数

#include<stdio.h>
#include<math.h>
double worm[111];
void qsort(int l,int r)    //快速排序     最好用优先队列（但是我不会用C写优先队列，C++中有STL，可以直接用）
                                          //每次取最大的2个数

{
             int i,j;
             double temp;
             if(l<r)
             {
                     i=l;
                     j=r;
                     temp=worm[l];

                     while(i<j)
                     {
                           while(i<j&&worm[j]>=temp)
                                    j--;
                           if(i<j)
                              worm[i++]=worm[j];
                           while(i<j&&worm[i]<temp)
                                    i++;
                          if(i<j)
                              worm[j--]=worm[i];
                     }
                 worm[i]=temp;
                 qsort(l,i-1);
                 qsort(i+1,r);
            }
}
int main(void)
{
              int i,N; 
              scanf("%d",&N);
              for(i=0;i<N;i++)
                   scanf("%lf",&worm[i]);
             qsort(0,N-1);
             while(N>1)
             {
                        worm[N-2]=2*sqrt(worm[N-1]*worm[N-2]);
                        N--;
                       qsort(0,N-1);
             }
             printf("%.3lf\n",worm[0]);
}

这篇关于poj 1862 贪心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---