C ++で配列積が大きくなるように、すべての配列要素を割り当てるための最小値を見つけます

n個の要素の配列があるとします。指定された配列のすべての要素を、arr [i]=xとなるような最小値xに更新します。新しい配列のすべての要素の積が、最初の配列のすべての要素の積よりも厳密に大きくなるようにします。ここで、i <=arr [i] <=10 ^ 10、および1 <=n <=10^5です。したがって、配列が[4、2、1、10、6]のような場合。したがって、4が最小の要素です。 4 * 4 * 4 * 4 * 4> 4 * 2 * 1 * 10 * 6

n個の要素の積がPであることがわかっているので、Pのn番目のルートを見つける必要がある場合、積のn番目のルートを見つけるには、配列のn個の要素の対数の合計からnを除算し、次に真数の上限を求めます。結果になります。

res =ceil（antilog（log（x）/ 10））

またはres=ceil（10 ^（log（x）/ 10））

例

#include <iostream>
#include <cmath>
#define EPS 1e-15
using namespace std;
long long findMinValue(long long arr[], long long n) {
   long double sum = 0;
   for (int i=0; i<n; i++)
   sum += (long double)log10(arr[i])+EPS;
   long double xl = (long double)(sum/n+EPS);
   long double res = pow((long double)10.0, (long double)xl) + EPS;
   return (long long)ceil(res+EPS);
}
int main() {
   long long arr[] = {4, 2, 1, 10, 6};
   long long n = sizeof(arr)/sizeof(arr[0]);
   cout << "Min value is: "<< findMinValue(arr, n);
}

出力

Min value is: 4