完美等比数列

也没想到什么技巧，就死算，，，

从公比q=1开始算，算出代价值后与原值对比，再递增q重复，一直算到某个临界值为止，，，

那q要算到多少为止，大概可以猜一下：代价值超过q为1时的代价值时为止。因为再怎么算都不能比这个值大。

怎么证明的单调性？猜的，感觉，结果对就行，，，

总和不超过上限，单项值不超过上限，运行到底就行。

代码：

#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;
}

这么解总感觉逻辑不完整，但是想不到什么好方法，，，

/*

    60%，不能再多了

*/

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
long long arr[maxn],cursum = 0;
int main()
{
    long long n,res = 0;
    cin>>n;
    for(int i = 0;i < n;++i)
        cin>>arr[i];
    if(n == 1)
    {
        cout<<0<<endl;
        return 0;
    }
    sort(arr,arr+n);
    
    for(int i =0;i < n;++i)
        cursum += arr[i];
    int q = 2;
    for(int i = 2;i < 10;++i)
    {
        long long sum1 = (pow(i,n)-1)/(i-1);
        if(sum1 == cursum)
        {
            q = i;
            break;
        }
        long long sum2 = (pow(i+1,n)-1)/(i);
         if(sum2 == cursum)
        {
            q = i+1;
            break;
        }
        if(sum1 < cursum && cursum < sum2)
        {
            if((cursum - sum1) < (sum2 - cursum))
                q = i;
            else
                q = i+1;
            break;
        }
        
    }
    
   
    
    for(int i = 0;i < n;++i)
    {
        res += abs(pow(q,i) - arr[i]);
    }
    cout<<res;
    
    
    return 0;
}