Codeforces Round #666 (Div. 2)B. Power Sequence（等比数列）

problem

给出一个数列
两个操作 交换位置或者+1 -1 使数列成为首项为1的等比
求最少操作次数

solution

• 考虑到等比数列一定递增，直接排序
• （过渡）试想特殊情况，排序后如果知道公比，那直接O(n)统计就好了，这显然是不可能的，所以要枚举公比，计算复杂度OK，一遍过。
• 枚举可能的公比，每次扫一遍统计需要的次数。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int a[100100];
int main(){
	int n; cin>>n;
	for(int i = 1; i <= n; i++)cin>>a[i];
	sort(a+1,a+n+1);
	LL ans = 1e18, lim = pow(1e18,1.0/n);//sqrt_n(18)
	for(int i = 1; i <= lim; i++){
		LL tmp = 0, k = 1;
		for(int j = 1; j <= n; j++){
			tmp += abs(k-a[j]);
			k *= i;
		}
		ans = min(ans,tmp);
	}
	cout<<ans<<'\n';
	return 0;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/108345480