在C++中找到最小值,以便数组乘积变大
假设我们有一个包含n个元素的数组。将给定数组的所有元素更新为某个最小值x,使得arr[i] = 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个元素的对数之和,然后取反对数的上限即可得到结果。
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
广告