一道水題，貪心 給你n個數(shù)字，每兩個數(shù)字以2sqrt(a*b)的方式合并成一個數(shù)，最后n個數(shù)字全部合并成一個數(shù)字，問最小的結果。
思路：四個數(shù)字abcd，按abcd 的順序合并，最后的結果等于2sqrt(d*2sqrt(c*2sqrt(b*a)))，可以看出，最先合并的數(shù)字被開根號的次數(shù)最多，所以越大的數(shù)字應該越靠里面，也就是越大的數(shù)字越先合并。 所以先排序，從大到小一個個合并
#include<cmath>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int MAXN = 105;double a[MAXN];int n;int main(){ while(scanf("%d", &n) == 1) { for(int i=0; i<n; i++) scanf("%lf", a+i); sort(a, a+n); double ans = a[n-1]; for(int i=n-2; i>=0; --i) ans = 2 * sqrt(ans*a[i]);新聞熱點
疑難解答
