我们称一个等比数列为完美等比数列,其应该满足首项为1,公比为正整数。
现有一个数列,A[1], A[2], ... , A[i], ... , A[N-1], A[N],可以对其进行如下两种操作:
1,交换任意两个数的位置,操作的代价为 0。
2,对其中一个数,加一或者减一,每次操作的代价为 1。
则对现有数列,若想将其调整成为“完美等比数列”,最小的代价是多少?
我们称一个等比数列为完美等比数列,其应该满足首项为1,公比为正整数。
现有一个数列,A[1], A[2], ... , A[i], ... , A[N-1], A[N],可以对其进行如下两种操作:
1,交换任意两个数的位置,操作的代价为 0。
2,对其中一个数,加一或者减一,每次操作的代价为 1。
则对现有数列,若想将其调整成为“完美等比数列”,最小的代价是多少?
输入数据:
输入数据包括两行。
第一行为一个数N,代表现有数列的长度。
第二行包括N个数,依次为 A[1], A[2], ... , A[i], ... , A[N-1], A[N]。
输入数据保证3 <= N <=100000, 1 <= A[i] <= 1000000000
输出数据:
输出数据一共1行,包括一个非负整数,代表调整A数列为“完美等比数列”,所需的最小代价。
4 5 5 5 5
11
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int N; cin >> N; vector<long> A; long n; while (N--) { cin >> n; A.push_back(n); } sort(A.begin(), A.end()); long limit = (A.back() - 1) * A.size(); long res = limit; long q = 1; long cost = 0; for (; cost <= limit; q++) { long x = 1; cost = 0; for (long a : A) { cost += abs(a - x); if (x > limit) { break; } else { x *= q; } } if (cost < res) res = cost; } cout << res << endl; }