首页 > 试题广场 >

完美等比数列

[编程题]完美等比数列
  • 热度指数:157 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解

我们称一个等比数列为完美等比数列,其应该满足首项为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数列为“完美等比数列”,所需的最小代价。

示例1

输入

4
5 5 5 5

输出

11
也没想到什么技巧,就死算,,,

从公比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;
}

这么解总感觉逻辑不完整,但是想不到什么好方法,,,
编辑于 2021-09-02 17:07:42 回复(0)
/*
    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;
}

编辑于 2021-08-30 18:11:04 回复(0)